[剑指Offer] Day 20: Divide and Conquer

Authored by Tony Feng

Created on May 1st, 2022

Last Modified on May 1st, 2022

Task 1 - Q07. 重建二叉树

Question

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

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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 or not inorder:
            return None

        # Find the root
        root = TreeNode(preorder[0]) 
        id = inorder.index(root.val)

        root.left = self.buildTree(preorder[1:id+1], inorder[0:id])
        root.right = self.buildTree(preorder[id+1:], inorder[id+1:])

        return root

Explanation

Preorder: root | left | right
Inorder: left | root | right
Root is the first element in preorder list.
Root in inorder list separates the left and right sub-trees.
Time Complexity: O(N)
Space Complexity: O(N)

Task 2 - Q16. 数值的整数次方

Question

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xⁿ）。不得使用库函数，同时不需要考虑大数问题。

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        elif n < 0:
            return 1 / self.myPow(x, -n) # Make n from negative to positive
        elif n & 1 == 0: # Even or not
            return self.myPow(x*x, n>>1) # i.e. n//2. It ensures the result is an integer. 
        else:
            return x * self.myPow(x, n-1)

Explanation

Time Complexity: O(log(N))
Space Complexity: O(log(N))

Task 3 - Q33. 二叉搜索树的后序遍历序列

Question

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

1
2
3
4
5
6
7


输入: [1,6,3,2,5], 输出: False
输入: [1,3,2,6,5], 输出: True
     5
    / \
   2   6
  / \
 1   3

Solution

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


class Solution:
    def verifyPostorder(self, postorder: [int]) -> bool:
        def recur(l, r):
            if l >= r: return True

            p = l
            while postorder[p] < postorder[r]:
                p += 1
            m = p

            while postorder[p] > postorder[r]:
                p += 1

            return p == r and recur(l, m-1) and recur(m, r-1)
        
        return recur(0, len(postorder)-1)

Explanation

The leftest node is always the root.
We need to find the serparator who divides the left and right sub-trees.
Time Complexity: O(N²), i.e., the shape is like a linked list.
Space Complexity: O(N), i.e., the shape is like a linked list.