二叉树遍历用递归的方式比较简单,但是迭代还是稍微有点绕,记录一下二叉树迭代遍历的统一框架,以防忘记:
主要的思路依旧是栈解决,但是为了当前栈顶元素是否需要被加入到result list中,巧妙地在需要被加入到result list中的元素之前加上一个null以示区分。
代码如下:
/** * 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> res = new LinkedList<>(); Stack<TreeNode> stack = new Stack<>(); if(root == null) return res; stack.push(root); while(stack.size() > 0){ TreeNode cur = stack.pop(); if(cur != null){ //先push右节点,因为stack具有FIFO的特性 if(cur.right != null) stack.push(cur.right); //push当前节点,并且用null标记 stack.push(cur); stack.push(null); //push左节点 if(cur.left != null) stack.push(cur.left); } //如果当前栈顶元素为null,则说明需要加入到list当中 else{ res.add(stack.pop().val); } } return res; } }
先序和后序只需要调整左中右三个节点的入栈顺序,非常方便。