剑指offer（五）

剑指offer（21-25）。

栈的压入和弹出序列

题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，
请判断第二个序列是否可能为该栈的弹出顺序。
假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，
序列4,5,3,2,1是该压栈序列对应的一个弹出序列，
但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

思路

1. 借用一个辅助栈

代码实现

class Solution:
    def IsPopOrder(self, pushV, popV):
        if len(pushV)!=len(popV): #如果入栈序列和弹出序列长度不一致，返回False
            return False
        stack=[]                 #创建一个辅助栈
        for i in pushV:          #循环将入栈序列的值压入辅助栈
            stack.append(i)
            while stack and stack[-1]==popV[0]: #如果辅助栈不为空并且辅助栈顶元素等于弹出序列第一个值
                stack.pop()                     #辅助栈栈顶元素出栈
                popV.pop(0)                     #弹出序列第一个值弹出
        if stack:                               #如果入栈序列循环结束，辅助栈不为空，说明弹出序列不是该栈的弹出顺序
            return False
        return True

从上往下打印二叉树

题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。

思路

1. 其实就是二叉树的层次遍历，借用一个队列就可以实现

代码实现

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

#其实就是对二叉树进行层次遍历，借用一个队列就可以实现
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        if not root:            #树为空，返回空列表
            return []
        result=[]              #存储好遍历结点值的列表
        queue=[root]           #辅助队列
        while queue:
            tmp=queue.pop(0)           #队头结点出队
            result.append(tmp.val)     #队头结点值存入列表
            if tmp.left:               #左子树非空，入队
                queue.append(tmp.left)
            if tmp.right:              #右子树非空，入队
                queue.append(tmp.right)
        return result

二叉搜索树的后序遍历序列

题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

思路

1. 后序遍历的序列中,最后一个数字是树的根节点 ,数组中前面的数字可以分为两部分：
   第一部分是左子树节点的值都比根节点的值小,第二部分是右子树节点的值都比根节点的值大，
   后面用递归分别判断前后两部分 是否 符合以上原则

代码实现

class Solution:
    def VerifySquenceOfBST(self, sequence):
        if not sequence:                     # 如果数组为空，直接返回False
            return False
        length=len(sequence)                #数组的长度
        root=sequence[-1]                   #根节点的值
        for i in range(length):             #寻找二叉搜索树的左子树
            if sequence[i]>root:
                break
        for j in range(i,length):           #判断二叉搜索树的右子树的每一个结点的值是否都比很结点大
            if sequence[j]<root:
                return False
        left=right=True                     # 递归调用，分别查看二叉树的左右子树
        if i>0:
            left=self.VerifySquenceOfBST(sequence[0:i])
        if i<length-1 and left:
            right=self.VerifySquenceOfBST(sequence[i:-1])
        return left and right               #当左右两子树都返回 True 的时候，结果才是 True

二叉树中和为某一值的路径

题目描述
输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
(注意: 在返回值的list中，数组长度大的数组靠前)

思路

1. 递归

代码实现

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        if not root:                #如果树为空，返回空列表
            return []
        result=[]
        if not root.left and not root.right and expectNumber==root.val: #节点为叶子节点且值等于给定值
            return [[root.val]]                                         #注意返回的是二维列表
        else:
            left=self.FindPath(root.left,expectNumber-root.val)         #递归查找左右子树中的路径（值要减去根节点的值）
            right=self.FindPath(root.right,expectNumber-root.val)
        for i in left+right:                                            #与根节点合并
            result.append([root.val]+i)
        return sorted(result, key=lambda x: -len(x))                    #输出按路径长度降序的列表，这里直接调用sorted函数
                                                                        #也可以自己编写一个排序函数，然后调用

复杂链表的复制

题目描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。
（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路

1. 递归
2. 非递归。

复制原来的链表，顺次链接成新的链表；
利用原来结点的random指向，来为复制的结点指向相应的random
将复制好的链表拆分出来，或者说将偶数位的节点重新拆分合成新的链表，得到的就是复制的链表

代码实现

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 pHead

    #复制原来的链表。顺次连接成新的链表
        cloNode=pHead
        while cloNode:
            node=RandomListNode(cloNode.label)
            node.next=cloNode.next
            cloNode.next=node
            cloNode=node.next

    #利用原来结点的random指向，来为复制的结点指向相应的random
        cloNode=pHead
        while cloNode:
            node=cloNode.next
            if cloNode.random:
                node.random=cloNode.random.next
            cloNode=node.next

    #将复制好的链表拆分出来，或者说将偶数位的节点重新拆分合成新的链表，得到的就是复制的链表
        cloNode=pHead
        pHead=pHead.next              #必须执行此操作，否则最后得到的pHead就是原链表的头结点了
        while cloNode.next:
            node=cloNode.next
            cloNode.next=node.next
            cloNode=node

        return pHead

#方法二，递归
class Solution2:
    # 返回 RandomListNode
    def Clone(self, pHead):
        if not pHead:
            return None
        cloneHead = RandomListNode(pHead.label)
        cloneHead.random = pHead.random
        cloneHead.next = self.Clone(pHead.next)
        return cloneHead