题解 | #二叉树的下一个结点#

# -*- 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