【迭代】【前序中序后序遍历】【指针】【Collections.reverse翻转数组】Leetcode 94 144 145

本文主要是介绍【迭代】【前序中序后序遍历】【指针】【Collections.reverse翻转数组】Leetcode 94 144 145，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【迭代】【前序中序后序遍历】Leetcode 94 144 145

- 1.前序遍历（递归） preorder
- 2.中序遍历（递归）inorder
- 3.后序遍历（递归）postorder

---------------🎈🎈题目链接前序遍历🎈🎈-------------------
---------------🎈🎈题目链接中序遍历🎈🎈-------------------
---------------🎈🎈题目链接后序遍历🎈🎈-------------------

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;}
}