LeetCode 94. Binary Tree Inorder Traversal

[Woodyiiiiiii]

二叉树的先序，中序，后序遍历是有关二叉树算法题目的基础/入门问题，递归解法不用说，迭代解法是我们需要十分关注的。

迭代解法对我们来说都不难，主要是如何去理解，弄清楚如何分类。隔了很久时间内我做了一遍三种遍历的迭代解法，发现中序遍历我遇到了些问题(/(ㄒoㄒ)/~~)，所以特意记录中序和后序遍历的解法，至于前序遍历太简单了所以不再记录。

(无题目)

首先是中序遍历，其思路是：利用一个栈，先将根节点压进栈中。首先从根节点一路沿着其左孩子节点，直至本身非空且左孩子节点为空，经过一个节点都要把它压入栈中。然后从栈中取出栈顶节点，其关键字加入结果集合中，接着从其右孩子节点开始继续重复沿着左孩子节点的过程。重复前两者过程，直至栈为空。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        while (!s.empty()) {
            if (root != null && root.left != null) {
                root = root.left;
                s.push(root);
                continue;
            }
            root = s.pop();
            res.add(root.val);
            root = root.right;
            if (root != null) {
                s.push(root);
            }
        }
        return res;
    }
}

注意，我们从栈顶取出节点，直接定位到这个节点的右孩子节点再push，不能像下面这样写：

           root = root.right;
            if (root != null) {
                s.push(root);
            }

接着是后序遍历，利用两个栈，最后第二个栈中节点的数值就是按照后序遍历结果的数值。我们先对二叉树进行先序遍历过程，把节点压入第一个栈中，然后把节点压入第二个栈中，继续从第一个栈顶取出节点，重复过程，直至第一个栈为空。(个人觉得后序遍历比中序遍历解法更简单清晰)

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> s1 = new Stack<>(), s2 = new Stack<>();
        s1.push(root);
        while (!s1.empty()) {
            root = s1.pop();
            if (root.left != null) s1.push(root.left);
            if (root.right != null) s1.push(root.right);
            s2.push(root);
        }
        while (!s2.empty())
            res.add(s2.pop().val);
        return res;
    }
}

---

参考资料：

• https://leetcode.com/problems/binary-tree-inorder-traversal/
• https://leetcode.com/problems/binary-tree-postorder-traversal/