剑指 二叉树中序遍历下一个节点

通过将出现的节点类型，分类，然后输出结果
如果当前节点存在右子树，那么下一个节点就是右子树中没有第一个左子树的节点，也就是最左的节点。
如果当前节点不存在右子树，那么下一个节点是父节点往上搜索中，为其父节点左节点的节点，返回其父节点。如果没有满足条件的那么就返回None

class Solution:
    def GetNext(self, pNode):
        # write code here
        if not pNode:
            return None
        if pNode.right:
            l=pNode.right
            while l.left!=None:
                l=l.left
            return l
        while pNode.next:
            l=pNode.next
            if l.left==pNode:
                return l
            pNode=pNode.next
        return None

先找到根节点，然后根据根节点进行中序遍历，放入数组中，根据当前节点寻找下一个节点。时间复杂度O(n)
空间复杂度O(n)

class Solution:
    def GetNext(self, pNode):
        # write code here
        if not pNode:
            return None
        l=pNode
        while l.next:
            l=l.next
        result=[]
        def inorder(r):
            if not r:
                return 
            if r.left:
                inorder(r.left)
            result.append(r)
            if r.right:
                inorder(r.right)
        inorder(l)
        for i in range(len(result)):
            if result[i]==pNode:
                if i<len(result)-1:
                    return result[i+1]
                else:
                    return None