173. Binary Search Tree Iterator

二叉搜索树的中序遍历，定义一个self.p指针，永远指向下一个节点。思路是左边的节点全部一次性进栈，完成后，pop最上面的节点A，检查它是否有右节点，如果有的话就作为下一个遍历的根节点，因为此节点的值大于A小于A的父节点。如果A没有右节点，说明没有值在A和A的父节点之间，那么直接popA的父节点作为答案。

class BSTIterator(object):

    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.stack = []
        self.p = root
        while self.p:
            self.stack.append(self.p)
            self.p = self.p.left


    def next(self):
        """
        @return the next smallest number
        :rtype: int
        """
        if self.stack or self.p:
            while self.p:
                self.stack.append(self.p)
                self.p = self.p.left
            else:
                next_node = self.stack.pop()
                self.p = next_node.right
                return next_node.val if next_node else None

    def hasNext(self):
        """
        @return whether we have a next smallest number
        :rtype: bool
        """
        if not self.stack and not self.p:
            return False
        return True

java用linkedlist做，注意判空不要直接像python一样和null比较。。

class BSTIterator {
    private LinkedList<TreeNode> stack;
    private TreeNode root;

    public BSTIterator(TreeNode root) {
        stack = new LinkedList<>();
        this.root = root;
        while (this.root != null) {
            stack.push(this.root);
            this.root = this.root.left;
        }
    }

    /**
     * @return the next smallest number
     */
    public int next() {
        if (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            if (root == null) {
                TreeNode nextNode = stack.pop();
                root = nextNode.right;
                return nextNode.val;
            }
        }
        return 0;
    }

    /**
     * @return whether we have a next smallest number
     */
    public boolean hasNext() {
        if (stack.isEmpty() && root == null) {
            return false;
        }
        return true;
    }
}

一个例子：检查左边的None后pop(1),检查右边的None后pop(3)

inorder的递归写法，思路就是按照左中右的处理顺序(左边处理完了，将左边的节点放入结果，上述图例中按照1111231...的顺序执行)

    def inorderTraversal(self, root):
        res = []
        self.dfs(root, res)
        return res

    def dfs(self, root, res):
        if not root:
            return

        self.dfs(root.left, res)  #1
        res.append(root.val)      #2
        self.dfs(root.right, res) #3