面试题 04.06. 后继者

设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。

如果指定节点没有对应的“下一个”节点，则返回null。

示例 1:

输入: root = [2,1,3], p = 1

输出: 2

示例 2:

输入: root = [5,3,6,2,4,null,null,1], p = 6

输出: null

Python 解答：
1.中序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        node = None
        res = None
        def isfind(root, p):
            if not root:
                return 
            else:
                isfind(root.left, p)
                nonlocal node, res
                if node:
                    if node == p:
                        res = root
                node = root
                if res:
                    return 
                isfind(root.right, p)
        isfind(root, p)
        return res

2.利用二叉搜索树的性质

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        if p.right:
            q = p.right
            while q:
                pre = q
                q = q.left
            return pre
        else:
            q = root
            pre = None
            while q != p:
                if q.val < p.val:
                    q = q.right
                elif q.val > p.val:
                    pre = q
                    q = q.left
            return pre

3.递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        if not root or not p:
            return None
        elif root.val <= p.val:
            return self.inorderSuccessor(root.right, p)
        else:
            q = self.inorderSuccessor(root.left, p)
            if not q:
                return root
            else:
                return q