【迭代】【前序中序后序遍历】Leetcode 94 144 145
---------------🎈🎈题目链接 前序遍历🎈🎈-------------------
---------------🎈🎈题目链接 中序遍历🎈🎈-------------------
---------------🎈🎈题目链接 后序遍历🎈🎈-------------------
1.前序遍历（递归） preorder
二叉树的前序遍历（中左右） 迭代法
入栈：顺序是中右左 这样保证出栈的时候可以是中 右 左
直到栈内全部遍历空为止
时间复杂度O(N)
空间复杂度O(N)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
// 迭代法 前序遍历 中左右
List<Integer> result = new ArrayList<>();
Stack<TreeNode> mystack = new Stack<>();
if(root == null){
return result;
}
mystack.push(root);
while(!mystack.isEmpty()){
TreeNode temp = mystack.pop();
result.add(temp.val);
if(temp.right != null){
//右
mystack.push(temp.right);
}
if(temp.left != null){
//左
mystack.push(temp.left);
}
}
return result;
}
}
2.中序遍历（递归）inorder
时间复杂度O(N)
空间复杂度O(N)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root == null) return result;
TreeNode cur = root;
while(!stack.isEmpty() || cur!=null){
// 当栈内不为空或者是当前元素不为null的时候 进行循环 也就是栈空且元素null的时候跳出循环
if(cur != null){
stack.push(cur);
cur = cur.left;
} else{
// 如果指针遍历到了叶子结点 就可以执行入栈出栈操作
cur = stack.pop();
result.add(cur.val);
cur = cur.right;
}
}
return result;
}
}
3.后序遍历（递归）postorder
迭代法，后续遍历就是在前序遍历的基础上，调换一下左右的顺序，
结束的时候利用Collections.reverse()翻转数组输出
时间复杂度O(N)
空间复杂度O(N)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
// 左右中
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root == null) return result;
stack.push(root);
while(!stack.isEmpty()){
TreeNode temp = stack.pop();
result.add(temp.val);
if(temp.left != null){
stack.push(temp.left);
}
if(temp.right != null){
stack.push(temp.right);
}
}
// 中右左 只需要result翻转输出即可得到 左右中
Collections.reverse(result);
return result;
}
}
