边工作边刷题：70天一遍leetcode: day 85-1

Inorder Successor in BST

要点：这题要注意的是如果不是BST，没法从树结构上从root向那边找p，只能遍历。而根据BST，可以只走正确方向

如果不检查right子树，可以从root到下，但invariant是root!=null。而检查右子树，invariant可以是root!=p

错误点：

不是找到某个>p.val，而是要找到最接近的p.val：所以loop终止条件是直到p==root or root is None，过程中只要>p.val就记录successor：这个过程的前提是p.right is None
别忘了loop

https://repl.it/CfBm/1

# Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

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

# Hide Company Tags Pocket Gems Microsoft Facebook

# Hide Tags Tree

# Hide Similar Problems (M) Binary Tree Inorder Traversal (M) Binary Search Tree Iterator

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution(object):

    def inorderSuccessor(self, root, p):

        """

        :type root: TreeNode

        :type p: TreeNode

        :rtype: TreeNode

        """

        if p.right:

            p = p.right

            while p.left:

                p=p.left

            return p

        else:

            succ = None

            while root!=p:

                if p.val<root.val:

                    succ = root

                    root = root.left

                else:

                    root = root.right

            return succ

边工作边刷题：70天一遍leetcode: day 85-1的相关教程结束。