Problem

Given a binary tree, return the inorder traversal of its nodes' values.

Example
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3


return [1,3,2].

思路(iterative)

1. 每当到达一个节点,
   1. 当前节点和左节点, 便存到栈中, 直到左子节点为空,
   2. 然后推出栈顶元素, 存到list中
   3. 将当前节点替换成它的右子节点, 重复以上步骤

    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            result.add(node.val);
            node = node.right;
        }
        return result;
    }

iterative version 2

    def inorderTraversal(self, root):
        res = []
        stack = []
        while root:
            stack.append(root)
            root = root.left
        while stack:
            curNode = stack.pop()
            res.append(curNode.val)
            node = curNode.right
            while node:
                stack.append(node)
                node = node.left
        return res