【剑指Offer】57二叉树的下一个结点

曾经终败给现在 2022-04-08 10:42 212阅读 0赞

## 题目描述 ##

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

时间限制：1秒；空间限制：32768K

## 解题思路 ##

中序遍历的遍历顺序是 左 -> 根 -> 右。

分三种情况讨论：

1，二叉树为空，则返回空

2，当前节点的右子树存在，返回右子树的最左节点

3，当前节点的右子树不存在，则找第一个当前节点是父节点左孩子的节点

# -*- coding:utf-8 -*-
    # class TreeLinkNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    #         self.next = None
    class Solution:
        def GetNext(self, pNode):
            # write code here
            # 二叉树为空，则返回空
            if pNode==None:
                return None
            # 如果有右子树，则找右子树的最左节点
            if pNode.right!=None:
                pNode = pNode.right
                while pNode.left!=None:
                    pNode = pNode.left
                return pNode
            # 没右子树，则找第一个当前节点是父节点左孩子的节点
            while pNode.next!=None:
                if pNode.next.left==pNode:
                    return pNode.next
                pNode = pNode.next
            # 退到了根节点仍没找到，则返回空
            return None

发表评论取消回复

表情：

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

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

相关阅读

相关 8.【剑指offer】二叉树的下一个结点

[题目][Link 1] 思路： 1. 找到根节点； 1. 存储中序遍历的结果到List集合中； 1. 遍历返回结点 / public cl

清疚/ 2024年03月26日 13:52/ 0 赞/ 90 阅读

相关剑指offer（C++）——二叉树的下一个结点

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 st

野性酷女/ 2022年06月17日 05:43/ 0 赞/ 169 阅读

相关《剑指offer》--008--二叉树的下一个结点

[《剑指offer》–目录索引][offer] 题目： > 给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？树中的结点除了有两个分别指向左右子结点的指针以

末蓝、/ 2022年05月27日 04:45/ 0 赞/ 202 阅读

相关剑指offer-题58：二叉树下的一个结点

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。实验平台：[牛客网][

待我称王封你为后i/ 2022年05月26日 01:14/ 0 赞/ 175 阅读

相关剑指Offer-二叉树的下一个结点

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。解题思路—回退遍历：要

朴灿烈づ我的快乐病毒、/ 2022年04月24日 13:18/ 0 赞/ 209 阅读

相关【剑指Offer】57二叉树的下一个结点

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。时间限制：1秒；空间限

曾经终败给现在/ 2022年04月08日 10:42/ 0 赞/ 213 阅读

相关【剑指Offer】（树）二叉树的下一个结点

题目链接：[https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=11

朴灿烈づ我的快乐病毒、/ 2022年03月16日 01:12/ 0 赞/ 230 阅读

相关剑指offer：二叉树的下一个结点

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 AC C++ Solu

客官°小女子只卖身不卖艺/ 2022年02月23日 04:24/ 0 赞/ 232 阅读

相关剑指offer 二叉树的下一个结点

[剑指offer题型分类及各题的代码及解题思路][offer] 题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不

迈不过友情╰/ 2021年10月14日 03:40/ 0 赞/ 313 阅读

相关剑指offer：二叉树的下一个结点

试题：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。代码：这一题的题意

傷城~/ 2021年06月24日 16:10/ 0 赞/ 391 阅读