牛客网习题集——剑指offer面试题第二部分（17-24）

17 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Son(self,pRoot1,pRoot2):
        if pRoot2 == None:
            return True
        if pRoot1 == None:
            return False
        if pRoot1.val != pRoot2.val:
            return False
        return self.Son(pRoot1.left,pRoot2.left) and self.Son(pRoot1.right,pRoot2.right)
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        result = False
        if pRoot1 != None and pRoot2 != None:
            if pRoot1.val == pRoot2.val:
                result = self.Son(pRoot1,pRoot2)
            if result == False:
                result = self.HasSubtree(pRoot1.left,pRoot2)
            if result == False:
                result = self.HasSubtree(pRoot1.right,pRoot2)
        return result

注意self的用法

所有的if 后的命令都会运行，而elif后面的命令是根据上一个if是否运行，如果运行了，elif则略过，否则才运行

二叉树的遍历，先查找根节点，再调用比较函数，利用递归

18 操作给定的二叉树，将其变换为源二叉树的镜像

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回镜像树的根节点
    def Mirror(self, root):
        # write code here
        if root == None :
            return
        tmp = root.left
        root.left = root.right
        root.right = tmp
        if root.left:
            self.Mirror(root.left)
        if root.right:
            self.Mirror(root.right)

掌握迭代的用法

20 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.assist = []
    def push(self, node):
        min = self.min()
        if not min or min>node:
            self.stack.append(node)
            self.assist.append(node)
        else:
            self.stack.append(node)
            self.assist.append(min)
    def pop(self):
        if self.stack:
            self.assist.pop()
            return self.stack.pop()   
    def top(self):
        if self.stack:
            return self.stack[-1]
    def min(self):
        if self.assist:
            return self.assist[-1]

采用辅助栈的技巧，保证辅助栈的上方始终是最小值

注意self的用法

注意append与pop，以及[]的使用

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

# -*- 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
        if not root:
            return []
        res = []
        deque = [root]
        while len(deque)>0:
            node = deque.pop(0)
            res.append(node.val)
            if node.left:
                deque.append(node.left)
            if node.right:
                deque.append(node.right)
        return res
                

广度优先搜索，本题关键是想到用队列解决

迭代的用法

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

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        if not sequence:
            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 = 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
       

找出后序遍历

迭代的用法

分清中括号与小括号的区别

注意点与逗号的区别

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

# -*- 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):
        res = []
        deeppath = self.dfs(root)
        for i in deeppath:
            if sum(map(int,i.split('->')))==expectNumber:
                res.append(list(map(int,i.split('->'))))
        return res
    def dfs(self,root):
        if not root:
            return []
        if not root.left and not root.right:
            return [str(root.val)]
        deeppath = [str(root.val) + "->" + spath for spath in self.dfs(root.left)]
        deeppath += [str(root.val) + "->" + spath for spath in self.dfs(root.right)]
        return deeppath

定义函数，分步解决

深度优先搜索的写法

sum，map,.split的用法

迭代的用法

未完待续。。