Leetcode笔记 每日一题 面试题 04.06. 后继者 (22.05.16)

Leetcode 每日一题 面试题 04.06. 后继者 (22.05.16)

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

如果指定节点没有对应的“下一个”节点，则返回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

题目求的是中序后继，即目标节点p的下一个节点的值并返回。我们可以理解为二叉树root中比目标节点p大的的节点中的最小一个。所以可以对root进行中序遍历，因为二叉搜索树的中序遍历，节点是从小到大依次排列的。然后判断中序遍历后是否存在root[i] == p，如果存在则返回root[i+1]，如果不存在则返回None

# 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:
        res = []  # 用来存储中序遍历的值
        # 中序遍历 -- 递归
        def inorder(root):
            if not root:
                return None
            inorder(root.left)
            res.append(root)
            inorder(root.right)
            return res
        inorder(root)
        for i in range(len(res)-1):
            if res[i] == p:
                return res[i+1]
        return None

另一种方法：可以用递归方法解决，参考：【负雪明烛】图解算法：思路 + 递归过程
根据二叉搜索树的性质：左子树的值会比当前节点小，右子树会比当前节点大。因此：

• 当root.val <= p.val时，我们要在当前root的右子树中寻找
• 如果root.val > p.val，则在左子树中寻找
• 如果不存在，则返回None

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