题解 | #二叉树的下一个结点#
二叉树的下一个结点
http://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e
# -*- coding:utf-8 -*-
#discuss according to different cases
# 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
#1-if pNone==None
if pNode==None:
print("null")
return None
#2-if pNone is not final leaf node:
if pNode.right !=None:
pNode=pNode.right
while pNode.left != None:
pNode=pNode.left
return pNode
elif pNode.next!=None:
if pNode==pNode.next.left:
return pNode.next
elif pNode==pNode.next.right:
pNode=pNode.next
if pNode.next==None:
return None
while pNode!=pNode.next.left:
pNode=pNode.next
if pNode.next==None:
return None
return pNode.next
# print("null")
return None
# print("null")
# return None
这道题思路很简单，就是分情况讨论：
1） 若节点有右子节点/右子树时，它的下一个节点是右子树的叶子左节点；
2）若节点无右子树时--->判断它是左节点还是右节点：是左节点（即pNode==pNode.next.left），下一个节点为它的父节点； 不是左节点(则是右节点)，则要沿着指针向上不断找父节点，直到这个大子树的根节点，即pNode==pNode.next.left
考虑边界测例：
节点为None时，返回None；
节点是整个树最后一个右叶子节点时，返回None
该树只有一个节点时（即pNode.next==None)，返回None
