题解 | #二叉树的下一个结点#
二叉树的下一个结点
http://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e
class TreeLinkNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
self.next = None
# 这题多个了一个子节点指向父节点的指针.
# 考虑一下,中序遍历的下一个节点分这样一些条件:
# 1. 如果该节点没有右孩子节点,则往上找父节点
# 1.1 如果该节点是其父节点的左节点,那么直接返回其父节点
# 1.2 如果该节点是其父节点的右节点,那么当前节点指向父节点,并继续向上找,
# 直到当前节点为其父节点的左节点,返回此时节点的父节点
# 2. 如果该节点存在右节点:
# 2.1 该右节点不再有左孩子节点,则下个节点就是它
# 2.2 该右节点还有左孩子节点,则继续向下找左孩子节点,直至找到的节点不再有左孩子
class Solution:
def GetNext(self, pNode: TreeLinkNode):
if not pNode.right:
tempnode = pNode
if pNode.next:
tempnodefu = pNode.next
else:
return None
while tempnode == tempnodefu.right:
tempnode = tempnodefu
tempnodefu = tempnodefu.next
if not tempnodefu:
return None
return tempnodefu
else:
tempnode = pNode.right
while tempnode.left:
tempnode = tempnode.left
return tempnode