本文共 1482 字,大约阅读时间需要 4 分钟。
我们以上图为例进行讲解,上图二叉树的中序遍历是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 = Noneclass 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