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

分手后的思念是犯贱 2022-11-09 01:27 122阅读 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 条评论，122人围观）

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

相关阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关面试：后端程序员面试题

面试：后端程序员面试题说明这篇文章翻译自一位外国友人的关于面试后端程序员的文章，我比较喜爱这篇文章。一是因为它极大的拓宽了我的视角，另一方面是其中的一些问

古城微笑少年丶/ 2022年11月06日 05:57/ 0 赞/ 159 阅读

相关 python后端开发面试题

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

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

相关 leetcode 面试题

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

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

相关 leetcode题后感-01

今天双11，断断续续的节日，望断天涯路！明年就要参加工作了，作为即将入职的菜鸟，倍感压力。得提前做好准备，刷刷算法题，让自己对java的理解有所提升，而且需要仔细体味jav

梦里梦外;/ 2022年08月10日 04:51/ 0 赞/ 9 阅读

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

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

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