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

树结构的遍历算法，注意回顾中序遍历等一些操作。解答这种题目的一些小经验

需要注意的事情有

1.了解定义的数据结构的各个元素值

2.熟悉各种递归调用结构，左右子树的递归调用算法流程

3.进行递归的分析过程

4.完成代码的相关编写过程

分析完成后，注意各种不满足题意的情况，返回相应的数值即可

# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    def __init__(self):
        node = []
        self.node = node  # 构架函数，定义一个全局变量
    def GetNext(self, pNode):
        # write code here，注意观察相应树的结构
        root = pNode
        while root.next:  # 下一个根节点还有的话
            root = root.next
        # 调用中序遍历函数，将数据进行遍历
        self.right_order(root)
        # 得到了相应的中序遍历的结果
        for i in range(len(self.node)-1):
            # 当前节点为
            cur = self.node[i]
            if pNode==cur:
                return self.node[i+1]
        # 其他的情况
        return None
        
        # 构造中序遍历的方法
    def right_order(self, root):
        if root==None:
            return
        # 左根右的次序将中序遍历结果
        self.right_order(root.left)
        self.node.append(root)  # 按顺序加入相应的根节点
        self.right_order(root.right)
            

完成相关的中序遍历代码编写

还需要编写相关的第二种方法，不返回中序遍历的结果，直接将相关的数据进行查找操作， 分三种情况进行讨论