LeetCode | 面试题 04.06. 后继者【Python】

问题

力扣

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

如果指定节点没有对应的“下一个”节点，则返回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：左子树不为空就去左子树找，否则当前节点就是中序后继节点

代码

Python3

# 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:
            return None

        # p >= root，后继节点在右子树
        if root.val <= p.val:
            return self.inorderSuccessor(root.right, p)
        else:
            # 左子树不为空
            if self.inorderSuccessor(root.left, p):
                return self.inorderSuccessor(root.left, p)
            # 左子树为空，当前节点就是后继节点
            else:
                return root

链接

GitHub