二叉树的下一个结点
题目描述
【二叉树的下一个结点】给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路
这里主要是分情况讨论结点的情况。
情况1： 结点有右孩子
找到右子树里面的最左结点，返回
情况2：结点没有右孩子，这时候有2个细分情况。
情况2.1： 结点是父节点的左子树
返回父节点
情况2.2： 结点是父节点的右子树
向上搜 不停的找结点的父节点 直到找到结点A，A的 父结点 的 左结点 是A。
返回A的父节点
代码
# 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 is None:
return None
#情况1： 结点有右孩子
#找到右子树里面的最左结点，返回
if pNode.right is not None:
pNode = pNode.right
while pNode.left is not None:
pNode = pNode.left
return pNode
#情况2.1： 结点是父节点的左子树
#返回父节点
elif pNode.next is not None and pNode.next.left == pNode:
return pNode.next
#情况2.2： 结点是父节点的右子树
# 向上搜 不停的找结点的父节点直到找到结点A，A的 父结点 的 左结点 是A。
# 返回A的父节点
elif pNode.next is not None and pNode.next.right == pNode:
while pNode.next is not None and pNode.next.left != pNode:
pNode = pNode.next
return pNode.next
return None
推荐阅读
- 热闹中的孤独
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
- 一个人的旅行，三亚
- 布丽吉特，人生绝对的赢家
- 慢慢的美丽
- 尽力
- 一个小故事，我的思考。
- 家乡的那条小河
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量