【剑指offer】 二叉树的下一个节点（python）

题目描述：

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

解题思路：
根据当前节点求二叉树中序遍历的下一节点，需要分成几种情况进行求解：
1、若当前节点存在右节点，则直接返回当前节点的右节点下的最后一个左节点。

		if pNode.right:
            temp = pNode.right
             # 若存在右节点，则返回右节点的下的最后一个左节点
            while temp.left:
                temp = temp.left
            return temp
        # 求解根节点

2、判断当前节点是否存在父节点
2.1 若当前节点存在父节点
2.1.1、在存在父节点的情况下，判断当前节点是否是左节点，如果是左节点，则直接返回当前节点的父节点

			if pNode.next.left and (pNode.next.left == pNode):
                return pNode.next

2.1.2、在存在父节点的情况下，判断当前节点是否是右节点
2.1.2.1 判断当前节点是否是最后一个右节点，如果是树的最后一个右节点，返回空

				while root.right:
                    root = root.right
                    # 若当前节点是最后一个右节点，则返回空
                    if pNode == root:
                        return None

2.1.2.2 若当前节点不是树的最后一个右节点，返回当前节点的父节点的父节点

return pNode.next.next

2.2 若当前节点不存在父节点，则返回空

return None

完整代码：

# -*- coding:utf-8 -*-
# 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.right:
            temp = pNode.right
             # 若存在右节点，则返回右节点的下的最后一个左节点
            while temp.left:
                temp = temp.left
            return temp
        # 求解根节点
        root = pNode
        while root.next:
            root = root.next
        # 判断父节点是否存在，即判断当前节点是否是根节点
        if pNode.next:
            # 在存在父节点的情况下，判断当前节点是否是左节点，
            # 如果是左节点，则直接返回当前节点的父节点
            if pNode.next.left and (pNode.next.left == pNode):
                return pNode.next
            # 在存在父节点的情况下，判断当前节点是否是右节点
            elif pNode.next.right and (pNode.next.right == pNode):
                # 判断当前节点是否是最后一个右节点
                while root.right:
                    root = root.right
                    # 若当前节点是最后一个右节点，则返回空
                    if pNode == root:
                        return None
                return pNode.next.next
        else:
            # 若当前节点的父节点不存在，则返回空
            return None