(python版)《剑指Offer》JZ57：二叉树的下一个结点

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了(python版)《剑指Offer》JZ57：二叉树的下一个结点，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1860字，纯文字阅读大概需要3分钟。

内容图文

牛客


我们以上图为例进行讲解，上图二叉树的中序遍历是d,b,h,e,i,a,f,c,g。我们以这棵树为例来分析如何找出二叉树的下一个结点。

• 如果一个结点有右子树，那么它的下一个结点就是它的右子树的最左子结点。也就是说从右子结点出发一直沿着指向左子树结点的指针，我们就能找到它的下一个结点。例如，图中结点b的下一个结点是h，结点a的下一个结点是f。

• 接着我们分析一下结点没有右子树的情形。如果结点是它父结点的左子结点，那么它的下一个结点就是它的父结点。例如，途中结点d的父节点(next)是b，f的父节点(next)是c。

• 如果一个结点既没有右子树，并且它还是父结点的右子结点，我们可以沿着指向父结点的指针一直向上遍历，直到找到一个是它父结点的左子结点的结点。
  如果这样的结点存在，那么这个结点的父结点就是我们要找的下一个结点。
  例如，为了找到结点g的下一个结点，我们沿着指向父结点的指针向上遍历，先到达结点c。由于结点c是父结点a的右结点，我们继续向上遍历到达结点a。由于结点a是树的根结点。它没有父结点。因此结点g没有下一个结点。

# -*- 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 not pNode:
            return None
        if not pNode.left and not pNode.right and not pNode.next:
            return None
        # 如果一个结点有右子树，那么它的下一个结点就是它的右子树的最左子结点
        if pNode.right:
            pNode = pNode.right
            while pNode.left:
                pNode = pNode.left
            return pNode
        
        # 如果没有右孩子但是有父节点
        while pNode.next:
            father = pNode.next
            if father.left == pNode:    # 若该节点是其父节点的左孩子
                return father           # 则下一节点就为父节点
            pNode = father              # 若该节点是其父节点的右孩子，找父节点的父节点，若到根节点(再无父节点了)，退出循环，返回None
        return None

# 若该节点是其父节点的右孩子，找父节点的父节点，若到根节点(再无父节点了)，退出循环，返回None

https://cuijiahua.com/blog/2018/01/basis_57.html
https://blog.csdn.net/u014568072/article/details/87910843

内容总结

以上是互联网集市为您收集整理的(python版)《剑指Offer》JZ57：二叉树的下一个结点全部内容，希望文章能够帮你解决(python版)《剑指Offer》JZ57：二叉树的下一个结点所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---