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

╰+哭是因爲堅強的太久メ 2022-05-19 05:50 56阅读 0赞

# 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
    class TreeLinkNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
            self.next = None
    class Solution:
        def GetNext(self, pNode):
            temp = None
            # 根节点的情况
            if(pNode.next == None):
                if (pNode.right != None):
                    temp = pNode.right
                    while temp.left != None:
                        temp = temp.left
                    return temp
                else:
                    return None
            # 是父节点的左孩子
            if pNode == pNode.next.left:
                temp = None
    
                if pNode.right != None:
                    temp = pNode.right
                    while temp.left != None:
                        temp = temp.left
                    return temp
                else:
                    return pNode.next
            # 是父节点的右孩子
            else:
                temp = None
                #  该节点还有右子树
                if pNode.right != None:
                    temp = pNode.right
                    while temp.left != None:
                        temp = temp.left
                    return temp
                # 该节点没有右子树（返回与该节点最近的一个拥有左孩子的父节点）
                else:
                    last = pNode
                    temp = pNode.next
                    while temp.next != None:
                        temp = temp.next
                        last = last.next
                        if temp.left == last:
                            return temp
                    # 上面的所用情况都不满足，即该节点为最后一个，返回None
                    return None
    a1 = TreeLinkNode(10)
    a2 = TreeLinkNode(5)
    a3 = TreeLinkNode(12)
    a4 = TreeLinkNode(4)
    a5 = TreeLinkNode(7)
    a1.left = a2
    a1.right = a3
    a3.left = a4
    a3.right = a5
    a1.next = None
    a2.next = a1
    a3.next = a1
    a4.next = a3
    a5.next = a3
    S = Solution()
    print S.GetNext(a2).val