[剑指Offer] Day 18: Search and Backtracking

Authored by Tony Feng

Created on April 29th, 2022

Last Modified on April 29th, 2022

Task 1 - Q55,I. 二叉树的深度

Question

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

Solution

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


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0

        depthL = self.maxDepth(root.left)
        depthR = self.maxDepth(root.right)
        
        return 1 + max(depthL, depthR)

Explanation

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

Task 2 - Q55,II. 平衡二叉树

Question

Solution 1

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


class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if not root:
            return True
        elif abs(self.getDepth(root.left) - self.getDepth(root.right)) <= 1:
            return self.isBalanced(root.left) and self.isBalanced(root.right)
        else:
            return False

    def getDepth(self, node): # A self-defined function to get the depth
        if not node: 
            return 0
        else:
            return 1 + max(self.getDepth(node.left), self.getDepth(node.right))

Solution 2

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


class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def recur(root):
            if not root: 
                return 0

            left = recur(root.left)
            if left == -1: 
                return -1 # -1 means the tree is imbalanced

            right = recur(root.right)
            if right == -1: 
                return -1
                
            return max(left, right) + 1 if abs(left - right) <= 1 else -1 

        return recur(root) != -1

Explanation

Solution 1
- Time Complexity: O(N * log(N))
  - I believe the worst case is when the tree is balanced, so the depth of the tree is log(N)
  - If the tree is like a linked list, the algorihtm will stop once the height difference exceeds 1 and will not go through the rest nodes of the tree.
  - getDepth: O(log(N))
  - isBalanced: O(N)
- Space Complexity: O(N)
Solution 2
- Time Complexity: O(N)
- Space Complexity: O(N)