Tree inorder iterator (带和不带parent pointer)

要求写一binary tree的 inorder interator.
但是这题跟以前见到的不太一样，这个给了一个parent pointer。
这样的话再用stack来做就不合适了。人家parent pointer都给你了， 你还说用stack不领情呀。
思路如下：
初始化的时候一路走到最左下角。
取值的时候返回当前结点上的值，当前结点为null时则返回null.
然后，由于是in order traversal，
1。 先判断这个点有没有右孩子。如果有孩子则把指针挪到右孩子的最左孩子。
2。 如果这个点没有右孩子。则我们要返回上一层了。
如果当前结点是它父亲的右孩子，则它的父亲也 是已经遍历过了，继续访问，直到当前结点不是它父亲的右孩子为止。

代码如下。

public class TreeNodeParent {

    int val;
    TreeNodeParent left, right, parent;

    public TreeNodeParent (int val) {
        this.val = val;
    }
}

class TreeIterator {
    TreeNodeParent node;
    public TreeIterator(TreeNodeParent root) {
        node = root;
        while (node.left != null) {
            node = node.left;
        }
    }
    public boolean hasNext() {
        return node != null;
    }
    public int next() {
        if (node == null) return -1;

        int ans = node.val;
        if (node.right != null) {
            node = node.right;
            while (node.left != null) node = node.left;
        } else {
            while (node.parent != null && node == node.parent.right) node = node.parent;
            node = node.parent;
        }
        return ans;
    }
}

再写一个不带parent pointer的。
由于没有parent pointer，这里要使用stack来做。

public class TreeNode {

    int val;
    TreeNode left, right;
    /*
    Constructor
     */
    public TreeNode(int val) {
        this.val = val;
    }
}

class InOrderIterator {
    Deque<TreeNode> stack;
    public InOrderIterator(TreeNode root) {
        stack = new LinkedList<>();
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    public TreeNode next(){
        if (!hasNext()) return null;
        TreeNode ans = stack.pop();
        if (ans.right != null) {
            TreeNode node = ans.right;
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
        }
        return ans;
    }
}