题解 | #二叉树的下一个结点#

二叉树的下一个结点

https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e

# -*- 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
        # 情况1:节点存在右子树,则打印右子树最左边的叶子结点即可
        if  pNode.right:
            pNode = pNode.right
            while pNode.left:
                pNode = pNode.left
            return pNode
        # 情况2:节点不存在右子树
        # 细分两种情况,节点属于父节点的左子树  右子树  两种情况
        # 情况2.1 节点属于父节点的左子树,那直接打印它的父节点即可
        # 情况2,.2 节点属于父节点的右子树,那就寻找其是否存在  上级节点是上上级节点的左子树
        # 这两种可以合并到一起,都属于2.2
        while pNode.next:
            if pNode.next.left == pNode:
                return pNode.next
            pNode = pNode.next
        return None

剑指offer刷题笔记 文章被收录于专栏

24秋招剑指offer刷题的笔记

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-08 14:08
点赞 评论 收藏
分享
05-12 17:00
门头沟学院 Java
king122:你的项目描述至少要分点呀,要实习的话,你的描述可以使用什么技术,实现了什么难点,达成了哪些数字指标,这个数字指标尽量是真实的,这样面试应该会多很多,就这样自己包装一下,包装不好可以找我,我有几个大厂最近做过的实习项目也可以包装一下
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 11:15
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务