Inorder Successor in Binary Search Tree

Note: If the given node has no in-order successor in the tree, return null.

这道题让我们求二叉搜索树的某个节点的中序后继节点，那么我们根据BST的性质知道其中序遍历的结果是有序的， 是我最先用的方法是用迭代的中序遍历方法，然后用一个bool型的变量b，初始化为false，我们进行中序遍历，对于遍历到的节点，我们首先看如果此时b已经为true，说明之前遍历到了p，那么此时我们返回当前节点，如果b仍为false，我们看遍历到的节点和p是否相同，如果相同，我们此时将b赋为true，那么下一个遍历到的节点就能返回了，参见代码如下：

Solution

最简单的方法就是先做一个递归的中序遍历，然后一个公共变量parent。

While 循环

class Solution(object):
    """
    @param root <TreeNode>: The root of the BST.
    @param p <TreeNode>: You need find the successor node of p.
    @return <TreeNode>: Successor of p.
    """
    def inorderSuccessor(self, root, p):
        if root is None or p is None:
            return None

        successor = None
        while root is not None and root.val != p.val: #p点的后继节点一定就是root.val > p.val
            if root.val > p.val:
                successor = root
                root = root.left
            else:
                root = root.right

        if root is None: #找不到p点的时候，跳出
            return None

        if root.right is None: #如果没有右节点，当前节点p==root 那么直接返回后续节点，就是从root过来的
            return successor

        root = root.right
        while root.left is not None: #如果有右节点，当前节点p==root 那么p点的后续是右子树的最小值，也就是最左左节点。
            root = root.left

        return root

Traverse: Traverse不需要返回任何，而是在不停的设置全局变量。常犯错误，默认写成了前序遍历，实际上是中序遍历。

class Solution(object):
    def inorderSuccessor(self, root, p):
        """
        :type root: TreeNode
        :type p: TreeNode
        :rtype: TreeNode
        """
        self.successor = None
        self.ancestor = None
        if root == None or p == None:
            return None
        self.inorderSuccessorHelper(root, p)
        return self.successor
    def inorderSuccessorHelper(self, root, p):
        if root == None:
            return
        self.inorderSuccessorHelper(root.left, p)
        if self.ancestor == p:
            self.successor = root
        self.ancestor = root
        self.inorderSuccessorHelper(root.right, p)