Tree Inorder Traversal

Recursive的解法

public void traversalInorder(TreeNode root) {
        if (root == null) return;
        traversalInorder(root.left);
        System.out.println(root.val);
        traversalInorder(root.right);
    }

Iterative的解法

    public void traversalInorderIterative(TreeNode root) {
        Deque<TreeNode> deque = new ArrayDeque<>();
        firstNode(deque, root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.pop();
            System.out.println(node.val);
            if (node.right != null) {
                firstNode(deque, node.right);
            }
        }
    }
    private void firstNode(Deque < TreeNode > stack, TreeNode root){
    //这个函数负责把当前结点push到最左边的孩子。
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }

带parent pointer的解法

class TreeTraversalParent {
    public TreeNodeParent firstNode(TreeNodeParent root) {
        if (root == null) return null;
        while (root.left != null) root = root.left;
        return root;
    }
    public TreeNodeParent nextNode(TreeNodeParent cur) {
        if (cur.right != null) return firstNode(cur.right);
        while (cur.parent != null && cur == cur.parent.right)  cur  = cur.parent;
        return cur.parent;
    }
}