# 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。

# 例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列

# -*- coding:utf-8 -*-

class Solution:

    def IsPopOrder(self, pushV, popV):

        # write code here

        # 1.建立一个辅助栈，将栈的压入序列压入到辅助栈中

        # 2.压入一个元素就与弹出序列进行比较，如果辅助栈顶元素与弹出序列相等就弹出

        # 3.最后判断辅助栈元素是否被完全弹出，如果完全弹出了返回true，否则返回FALSE；

        # 特殊情况

        if not pushV or len(pushV) != len(popV):

            return False

        stack = []

        # 1.建立一个辅助栈，将栈的压入序列压入到辅助栈中

        for ele in pushV:

            stack.append(ele)

            # 2.压入一个元素就与弹出序列进行比较，如果辅助栈顶元素与弹出序列相等就弹出

            while len(stack) and stack[-1] == popV[0]:

               # 注意：这里是pop()对应前面的append()

                stack.pop()

                popV.pop(0)

        if len(stack):

            return False

        return True

# -*- coding:utf-8 -*-

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    # 返回从上到下每个节点值列表，例：[1,2,3]

    def PrintFromTopToBottom(self, root):

        # write code here

        # 广度优先遍历

        # 创建一个队列（先进先出），用于保存树节点

        queue_ = [root]

        # 列表用于保存每个节点值

        list_ = []

        if not root:

            return []

        while queue_:

            node = queue_.pop(0)

            list_.append(node.val)

            # 依次遍历左右节点

            if node.left:

                queue_.append(node.left)

            # 注意：这里要用if，不能用if elif

            if node.right:

                queue_.append(node.right)

        return list_
            

# -*- coding:utf-8 -*-

class Solution:

    def VerifySquenceOfBST(self, sequence):

        # write code here

        # 后序遍历 的序列中，最后一个数字是树的根节点 ，数组中前面的数字可以分为两部分：

        # 第一部分是左子树节点 的值，都比根节点的值小；

        # 第二部分 是右子树 节点的值，都比 根 节点 的值大，后面用递归分别判断前后两部分 是否 符合以上原则

        # 特殊的

        if sequence == None or len(sequence) == 0:

            return False

        # 1、找到根节点

        length = len(sequence)

        root = sequence[length - 1]

        # 找到数组中小于根节点的值，左子树

        for i in range(length):

            if sequence[i] > root:

                # 跳出循环，此时i已经保存

                break

        #  找到数组中大于根节点的值，右子树

        for j in range(i, length):

            if sequence[j] < root:

                return False

        # 递归：判定节点的左/右 子树是否为二叉树

        left = True

        if i > 0:

            left = self.VerifySquenceOfBST(sequence[0:i])

        right = True

        if i < length - 1:

            right = self.VerifySquenceOfBST(sequence[i:-1])

        return left and right
        

# -*- coding:utf-8 -*-

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    # 返回二维列表，内部每个列表表示找到的路径

    def FindPath(self, root, expectNumber):

        # write code here

        # 输入为空树时，返回空列表

        if not root:

            return []

        # 到达叶子节点，并且叶子节点的值符合最后需要的那一个值，则返回该路径

        if not root.left and not root.right and root.val == expectNumber:

            return [[root.val]]

        # 非叶子节点时，如果当前节点值小于需要值，则继续遍历

        if root.val < expectNumber:

            # 遍历结果为左右子树遍历结果的集合

            x = self.FindPath(root.left, expectNumber - root.val) + self.FindPath(root.right, expectNumber - root.val)

            # 如果有结果则加上本节点并且对结果长度一次排序，否则返回空列表

            # return [[root.val, ] + each for each in x] if x else []

            return sorted([[root.val, ] + each for each in x], key = lambda x: len(x), reverse=True) if x else []

        # 非叶子节点时，如果当前节点值已经超过需要的数，则提前结束该分支的遍历

        else:

            return []

# -*- coding:utf-8 -*-

# class RandomListNode:

#     def __init__(self, x):

#         self.label = x

#         self.next = None

#         self.random = None

class Solution:

    # 返回 RandomListNode

    def Clone(self, pHead):

        if not pHead:

            return None

        # 复制头结点

        dummy = pHead

        # 1. 把复制的结点链接在原始链表的每一对应结点后面

        while dummy:

            dummynext = dummy.next

            # 每次循环新建一个节点（复制）

            copynode = RandomListNode(dummy.label)

            # 复制节点指向原结点的下一个结点

            copynode.next = dummynext

            # 原结点指向复制结点，完成插入

            dummy.next = copynode

            # 继续遍历下一对结点

            dummy = dummynext

        # 将dummy继续指向头结点

        dummy = pHead

        #  2. 把复制的结点的random指针指向被复制结点的random指针的下一个结点

        while dummy:

            # 得到原结点指向的随机结点

            dummyrandom = dummy.random

            # 得到原结点指向的复制结点

            copynode = dummy.next

            if dummyrandom:

                # 令复制结点的随机结点，指向原结点指向的随机结点的下一个结点

                copynode.random = dummyrandom.next

            # 进行下一组

            dummy = copynode.next

        # 3. 拆分成两个链表，奇数位置为原链表，偶数位置为复制链表，

        # 注意复制链表的最后一个结点的next指针不能跟原链表指向同一个空结点None，

        # next指针要重新赋值None(判定程序会认定你没有完成复制）

        # 将dummy继续指向头结点

        dummy = pHead

        # 将最终要返回的复制头结点，指向原头结点的下一个结点

        copyHead = pHead.next

        # 开始拆分

        while dummy:

            # 得到复制结点

            copyNode = dummy.next

            # 得到原结点的原下一个结点

            dummynext = copyNode.next

            # 将原结点指向原下一个结点

            dummy.next = dummynext

            if dummynext:

                # 复制结点指向它应该指向的

                copyNode.next = dummynext.next

            else:

                copyNode.next = None

            # 进行下一组

            dummy = dummynext

        # 返回复制后的头结点

        return copyHead