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

分手后的思念是犯贱 2022-11-09 01:27 146阅读 0赞

## 问题 ##

[力扣][Link 1]

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

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

[Link 1]: https://leetcode-cn.com/problems/successor-lcci/
[GitHub]: https://github.com/Wonz5130/LeetCode-Solutions/tree/master/solutions/Interview-04.06-Successor-LCCI

发表评论取消回复

表情：

评论列表（有 0 条评论，146人围观）

还没有评论，来说两句吧...

相关阅读

相关 python面试题——设计模式之观察者模式

![在这里插入图片描述][a386ee3272f64a8989d0c8096ab22b60.webp_pic_center] 1、观察者模式观察者模式：定义对象间的一

悠悠/ 2024年04月08日 09:58/ 0 赞/ 110 阅读

相关 LeetCode | 面试题 01.07. 旋转矩阵【Python】

> LeetCode 面试题 01.07. 旋转矩阵【Medium】【Python】【数学】问题 [力扣][Link 1] 给你一幅由 N × N 矩阵表示的图像，

浅浅的花香味﹌/ 2023年07月24日 14:59/ 0 赞/ 58 阅读

相关 Leetcode DFS_面试题 04.06. 后继者

Leetcode DFS\_面试题 04.06. 后继者 1、问题分析 2、问题解决 3、总结 1、问题分析本质上就是一个二叉树的遍历问题

￡神魔★判官ぃ/ 2023年03月14日 08:06/ 0 赞/ 8 阅读

相关每日算法：朋友圈、岛屿数量、合法二叉树、后继者

1、朋友圈班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的

短命女/ 2023年02月10日 08:01/ 0 赞/ 4 阅读

相关 LeetCode | 面试题 17.12. BiNode【Python】

问题 [力扣][Link 1] 二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链

落日映苍穹つ/ 2022年11月12日 10:59/ 0 赞/ 211 阅读

相关 LeetCode | 面试题 04.12. 求和路径【Python】

问题 [力扣][Link 1] 给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径

た入场券/ 2022年11月10日 00:46/ 0 赞/ 180 阅读

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

问题 [力扣][Link 1] 设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。如果指定节点没有对应的“下一个”节点，则返回null。示

分手后的思念是犯贱/ 2022年11月09日 01:27/ 0 赞/ 147 阅读

相关 python后端开发面试题

目录一：简述你对Restful风格的理解： 1：协议 : 2：域名： 3：版本：

悠悠/ 2022年10月31日 13:34/ 0 赞/ 227 阅读

相关 leetcode 面试题

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

我就是我/ 2022年09月02日 11:54/ 0 赞/ 258 阅读

相关 leetcode-top面试题阶乘后的零

题目给定一个整数 n，返回 n! 结果尾数中零的数量。示例 1: 输入: 3 输出: 0 解释: 3! = 6, 尾数中没有零。示例 2: 输

客官°小女子只卖身不卖艺/ 2021年11月23日 00:00/ 0 赞/ 295 阅读