大家好我是苏麟 , 今天带来二叉树的迭代遍历 .
描述 :
给你二叉树的根节点 root ,返回它节点值的 前序 遍历。
题目 :
LeetCode 二叉树的前序遍历 :

分析 :

前序遍历是中左右,如果还有左子树就一直向下找。完了之后再返回从最底层逐步向上向右找。 不难写出如下代码 :
解析 :
- /**
- * 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
preorderTraversal(TreeNode root) { -
- List
list = new ArrayList<>(); - if(root == null){
- return list;
- }
-
- Stack
stack = new Stack<>(); -
- TreeNode temp = root;
- while(!stack.isEmpty() || temp != null){
- while(temp != null){
- stack.add(temp);
- list.add(temp.val);
- temp = temp.left;
- }
- temp = stack.pop();
- temp = temp.right;
- }
- return list;
- }
- }
描述 :
给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。
题目 :
LeetCode 94.二叉树的中序遍历 :

分析 :
中序遍历,中序遍历是左中右,先访问的是二又树左子树的节点,然后一层一层向下访问,直到到达树左面的最底部,再开始处理节点(也就是在把节点的数值放进res列表中)。在使用迭代法写中序遍历,就需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素。
解析 :
- /**
- * 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
inorderTraversal(TreeNode root) { - List
list = new ArrayList<>(); - if(root == null){
- return list;
- }
- Stack
stack = new Stack<>(); - TreeNode node = root;
- while(!stack.isEmpty() || node != null){
- while(node != null){
- stack.push(node);
- node = node.left;
- }
- node = stack.pop();
- list.add(node.val);
- node = node.right;
- }
- return list;
- }
- }
描述 :
给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。
题目:
LeetCode 145.二叉树的后序遍历 :

分析 :
后序遍历,后序遍历是左右中,先访问的是二又树左子树的节点,然后一层一层向下访问,直到到达树左面的最底部,再开始处理节点(也就是在把节点的数值放进res列表中)。在使用迭代法写后序遍历,就需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素。
解析 :
- /**
- * 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
postorderTraversal(TreeNode root) { - List
list = new ArrayList<>(); - if(root == null){
- return list;
- }
-
- Stack
stack = new Stack<>(); - TreeNode node = root;
- while(!stack.isEmpty() || node != null){
- while(node != null){
- list.add(node.val);
- stack.push(node);
- node = node.right;
- }
- node = stack.pop();
- node = node.left;
- }
-
- Collections.reverse(list);
- return list;
-
- }
- }
这期就到这里 , 下期再见 !