[剑指Offer] Day 19: Search and Backtracking

Authored by Tony Feng

Created on April 30th, 2022

Last Modified on April 30th, 2022

Task 1 - Q64. 求1+2+…+n

Question

求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

Solution 1

1
2
3


class Solution: # built-in function
    def sumNums(self, n: int) -> int:
        return sum(range(1, n+1))

Solution 2

1
2
3


class Solution: # logical operation
    def sumNums(self, n: int) -> int:
        return n and (n + self.sumNums(n-1))

Explanation

Solution 1 & 2
- Time Complexity: O(N)
- Space Complexity: O(N)

Task 2 - Q68,I. 二叉搜索树的最近公共祖先

Question

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。题目中所有节点的值都是唯一的，p、q 为不同节点且均存在于给定的二叉搜索树中。

最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution: # Iteration
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while root:
            if root.val > p.val and root.val > q.val:
                root = root.left
            elif root.val < p.val and root.val < q.val:
                root = root.right
            else:
                break
        return root

Solution 2

1
2
3
4
5
6
7
8


class Solution: # Recursion
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

Explanation

Since it is a binary search tree, we could use its properties to solve the problem. And no duplicate nodes in the tree.
- The nodes in the left sub-tree are smaller than the root.
- The nodes in the right sub-tree are larger than the root.
Solution 1
- Time Complexity: O(N)
- Space Complexity: O(1)
Solution 2
- Time Complexity: O(N)
- Space Complexity: O(N)

Task 3 - Q68,II. 二叉树的最近公共祖先

Question

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

Solution

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


class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:

        if not root or root == p or root == q: 
            return root

        r = self.lowestCommonAncestor(root.right, p, q)
        l = self.lowestCommonAncestor(root.left, p, q)

        if not r and not l:
            return None
        elif r and not l:
            return r
        elif not r and l:
            return l
        else:
            return root

Explanation

If a node is the p and q’s lowest common ancestor:
- p, q exist in different sides of the node respectively.
- p is the node and q is in its sub-tree.
- q is the node and p is in its sub-tree.
Solution 1 & 2
- Time Complexity: O(N)
- Space Complexity: O(N)