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

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

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

相关阅读

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

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

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

相关 LeetCode | 面试题26. 树的子结构【Python】

> LeetCode 面试题26. 树的子结构【Medium】【Python】【DFS】问题 [力扣][Link 1] 输入两棵二叉树A和B，判断B是不是A的子结构

爱被打了一巴掌/ 2023年07月17日 02:41/ 0 赞/ 2 阅读

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

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

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

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

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

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

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

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

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

相关 LeetCode | 面试题 04.04. 检查平衡性【Python】

问题 [力扣][Link 1] 实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。示例 1:

野性酷女/ 2022年11月08日 14:11/ 0 赞/ 54 阅读

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

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

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

相关 python后端开发面试题

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

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

相关 leetcode 面试题

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

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

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

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

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