剑指 Offer 2022/7/1

剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]

代码思路

1. 递归建树
   直接操作列表

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def creat(p,q):
            if p==[] or p==None:
                return None
            root=TreeNode(p[0])
            pos=q.index(p[0])
            root.left=creat(p[1:pos+1],q[0:pos])
            root.right=creat(p[pos+1:],q[pos+1:])
            return root
        return creat(preorder,inorder)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2. 递归建树
   操作位置

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def build(p_l,p_r,i_l,i_r):
            root=TreeNode(preorder[p_l])
            if p_l==p_r:return root
            root_pos=inorder.index(preorder[p_l])
            l_len=root_pos-i_l
            if l_len-1>=0:root.left=build(p_l+1,p_l+l_len,i_l,root_pos-1)
            if p_r-(p_l+l_len+1)>=0:root.right=build(p_l+l_len+1,p_r,root_pos+1,i_r)
            return root
        n=len(preorder)
        if n==0:return None
        return build(0,n-1,0,n-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

剑指 Offer 09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：
输入：
[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[3],[],[]]
输出：[null,null,3,-1]

示例 2：
输入：
[“CQueue”,“deleteHead”,“appendTail”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

代码思路
在deleteHead中操作俩个栈

class CQueue:

    def __init__(self):
        self.a=[]
        self.b=[]

    def appendTail(self, value: int) -> None:
        self.a.append(value)


    def deleteHead(self) -> int:
        if self.b: return self.b.pop()
        if not self.a:return -1
        self.b=self.a[::-1]
        self.a=[]
        return self.b.pop()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16