【LeetCode】94. 二叉树的中序遍历（Java）

给定一个二叉树，返回它的中序 遍历。

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解法一

递归

/** * 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 { private List<Integer> res = new ArrayList<>(); public List<Integer> inorderTraversal(TreeNode root) { if (root == null) return res; //中序遍历 inorderTraversal(root.left); res.add(root.val); inorderTraversal(root.right); return res; } }

解法二

迭代

class Solution { public List<Integer> inorderTraversal(TreeNode root) { //迭代 List<Integer> res = new ArrayList<>(); //栈 Deque<TreeNode> stack = new ArrayDeque<>(); //cur代表遍历时当前的节点 TreeNode cur = root; while (!stack.isEmpty() || cur != null) { //一直走到最左叶子节点的左节点（即null） while (cur != null) { stack.push(cur); cur = cur.left; } //如果取出栈顶，即最左叶子节点，添加到res中 //然后赋值给cur最左叶子节点的右节点 //下个循环就是遍历最左叶子节点的右节点的左节点 //如果如果右节点为空，那么下个循环，上面遍历左节点的while就不会执行，直接到这里，再取一个节点，放到res后，再去遍历它的右节点 TreeNode temp = stack.pop(); res.add(temp.val); cur = temp.right; } return res; } }

前序遍历的迭代比较好理解，中序理解起来就难一些了。