[剑指Offer] Day 7: Searching and Backtracking

Authored by Tony Feng

Created on April 18th, 2022

Last Modified on April 18th, 2022

Task 1 - Q26. 树的子结构

Question

输入两棵二叉树A和B，判断B是不是A的子结构。若B是A的子结构，即A中有出现和B相同的结构和节点值。(约定空树不是任意一个树的子结构)

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if not B or not A: 
            return False

        def compare(nodeA, nodeB):
            if not nodeB: # Finish checking all nodes in B
                return True
            if not nodeA: # nodeA is empty but nodeB not
                return False
            return nodeA.val == nodeB.val and compare(nodeA.left, nodeB.left) and compare(nodeA.right, nodeB.right)

        return (compare(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))

Explanation

N = # of nodes in tree A; M = # of nodes in tree B
Time Complexity: O(N*M)
Space Complexity: O(N)
- The worst case is traversing the whole tree A.

Task 2 - Q27. 二叉树的镜像

Question

请完成一个函数，输入一个二叉树，该函数输出它的镜像。(类似于水平翻转)

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


class MySolution: # BFS
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None

        mRoot = TreeNode(root.val)
        que = [root]
        mQue = [mRoot]
        while que:
            node = que.pop(0)
            mNode = mQue.pop(0)
            if node.left:
                mNode.right = TreeNode(node.left.val)
                mQue.append(mNode.right)
                que.append(node.left)
            if node.right:
                mNode.left = TreeNode(node.right.val)
                mQue.append(mNode.left)
                que.append(node.right)
        return mRoot  

class Solution: # BFS
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root: 
            return
        stack = [root] # FILO
        while stack:
            node = stack.pop()
            if node.left: 
                stack.append(node.left)
            if node.right: 
                stack.append(node.right)
            node.left, node.right = node.right, node.left
        return root

Solution 2

1
2
3
4
5
6
7


class Solution: # Recursion
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root: 
            return
        root.left = self.mirrorTree(root.right)
        root.right = self.mirrorTree(root.left)
        return root

Explanation

My solution and solution 1 have the same idea, but the latter is more tricky.
Solution1 & 2
- Time Complexity: O(N)
- Space Complexity: O(N)

Task 3 - Q28. 对称的二叉树

Question

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def recur(L, R):
            if not L and not R: 
                return True
            if not L or not R: 
                return False
            return L.val == R.val and recur(L.left, R.right) and recur(L.right, R.left)

        return recur(root.left, root.right) if root else True   

Explanation

Time Complexity: O(N)
- The algorithm calls the recur() for N/2 times at most.
Space Complexity: O(N)