二叉树的下一个结点

题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路

这里主要是分情况讨论结点的情况。
情况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