leetcode [面试题04.06] 后继者

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

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

示例 1:

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

  2
 / \
1   3

输出: 2

示例 2:

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

      5
     / \
    3   6
   / \
  2   4
 /   
1

输出: null

注意判断条件，如果已经检测到的条件为flag为True并且ans有值。

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        ans = None
        flag = False
        def inorder(root):
            nonlocal ans, flag
            if not root or ans: return
            inorder(root.left)
            if flag and not ans:
                ans = root
                return
            if root == p:
                flag = True
            inorder(root.right)

        inorder(root)
        return ans