二叉树的中序遍历

---

LeetCode 94

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

解题思路

方法一：递归

List<Integer> res = new LinkedList<Integer>();
public List<Integer> inorderTraversal(TreeNode root) {
    if (root != null) {
        inorderTraversal(root.left);
        res.add(root.val);
        inorderTraversal(root.right);
    }
    return res;
}  

方法二：迭代

说明：递归在底层的实现就是运用栈，用迭代的方法只不过是把底层的栈显化出来。

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new LinkedList<Integer>();
    Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
    while (!stack.isEmpty() || root != null) {
        // 一直左子树深入，在这过程中遍历到的节点入栈
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.poll();
        res.add(root.val);
        root = root.right;
    }
    return res;
}