Python
二叉树的下一个结点
http://www.nowcoder.com/questionTerminal/9023a0c988684a53960365b889ceaf5e
时间复杂度为O(n),空间复杂度为O(1)
考虑两种情况，第一种目标结点有右子树，只需要找右子树的最左子结点即可；
第二种，目标结点没有左子树，向上遍历，找到目标结点父节点是其左孩子的结点即可；
反之返回None。
class Solution:
def GetNext(self, pNode):
# write code here
if not pNode:return None
if pNode.right:
pNode = pNode.right
while pNode.left:
pNode = pNode.left
return pNode
while pNode.next:
if pNode.next.left == pNode:
return pNode.next
pNode = pNode.next
return None
海康威视公司福利 403人发布