1. 剑指 Offer 07. 重建二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 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:
        if not preorder:return None 
        root = TreeNode(preorder[0])
        root_index = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:root_index+1],inorder[:root_index])
        root.right = self.buildTree(preorder[root_index+1:],inorder[root_index+1:])
        return root

2. 剑指 Offer 26. 树的子结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        def isRootSubStructure(A,B):
            if not B:return True
            if not A or A.val!=B.val:return False
            return isRootSubStructure(A.left,B.left) and isRootSubStructure(A.right,B.right)
        if not A or not B:return False
        if isRootSubStructure(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B):return True
        else:return False

3. 剑指 Offer 64. 求1+2+…+n

利用and短路来结束递归,and前为False时不做后面的判断

1
2
3
4
5
6
7
class Solution:
    def __init__(self):
        self.res=0
    def sumNums(self, n: int) -> int:
        n>1 and self.sumNums(n-1)
        self.res+=n
        return self.res