Tree Recursion

Algorithms
recursion, tree
Catalogue
  1. 1. Basic
    1. 1.1. 104. Maximum Depth of Binary Tree
    2. 1.2. 111. Minimum Depth of Binary Tree
    3. 1.3. 110. Balanced Binary Tree
    4. 1.4. 101. Symmetric Tree
    5. 1.5. 226. Invert Binary Tree
    6. 1.6. 100. Same Tree
    7. 1.7. 543. Diameter of Binary Tree
    8. 1.8. 222. Count Complete Tree Nodes

Basic

  • Binary tree 往往是最常见的，和recursion结合最紧密的面试题目类型

    • 树本身就是Recursive的结构！
    • 每层的node具备的性质，传递的值和下一层的性质往往一致。比较容易定义recursive rule
    • Base case(generally):null pointer under the leaf node, Base case usually refers to the null childNode below leaf.

  • Way of thinking (相当于后序遍历 - int ,bool,etc.)

    • 1.What do you expect from your lchild/rhild?
      (usually it is the return type of the recursion type)
    • 2.What do you want to do in the current layer?
    • 3.What do you want to report to your parent?(same as Q1 == Q3)

104. Maximum Depth of Binary Tree

  • 1 Child: 问左右两个孩子要一个值
  • 2 Current: 当前层拿到左右孩子的值可以做些处理
  • 3 Parent: 向父节点返回的值和child要的值要一样就接上了！！
1
2
3
4
5
6
7
8
9
# Time : O(n), Space : O(n)
# Post Order
class Solution(object):
    def maxDepth(self, root):
        if not root:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return max(left,right) + 1

111. Minimum Depth of Binary Tree

每个节点的状态可以划分为：

  • 叶子节点 - lchild is None, rchild is None
  • 有两个孩子 - lchild is not None, rchild is not None
  • 有一个孩子 - not left child OR not right child
1
2
3
4
5
6
7
class Solution(object):
    def minDepth(self, root):
        if not root:
            return 0
        if not root.left or not root.right:
            return self.minDepth(root.left) + self.minDepth(root.right) + 1
        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
  • 从下往上反值 - 统计tree里每个node的左子树有多少个node？
  • 从下往上返值 - Find the node with max difference in the total number of descendents in its left subtree and right subtree

110. Balanced Binary Tree

A binary tree in which the depth of the two subtrees of every node never differ by more than 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Time : O(nlogn), Space : O(n)
class Solution(object):
    def height(self, root):
        if not root:
            return 0
        return max(self.height(root.left), self.height(root.right)) + 1

    def isBalanced(self, root):
        if not root:
            return True
        left = self.height(root.left)
        right = self.height(root.right)
        if abs(left-right) > 1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Time : O(n), Space : O(n)
class Solution(object):
    def isBalanced(self, root):
        return self.dfs(root) != -1

    def dfs(self, root):
        if not root:
            return 0
        left = self.dfs(root.left)
        if left == -1:  return -1

        right = self.dfs(root.right)
        if right == -1: return -1

        if abs(left - right) > 1:
            return -1
        return max(left, right) + 1

101. Symmetric Tree

  • 判断空间复杂度的时候一定要注意树不一定是balanced的！！！
1
2
3
4
5
6
7
8
9
10
11
12
13
# Time : O(n), Space : O(n)
class Solution(object):
    def isSymmetric(self, root):
        return self.isMirror(root, root)
    def isMirror(self, root1, root2):
        if not root1 and not root2:
            return True
        elif not root1 or not root2:
            return False
        else:
            return ( root1.val == root2.val
                and self.isMirror(root1.left, root2.right)
                and self.isMirror(root1.right, root2.left))

226. Invert Binary Tree

  • 注意赋值的过程已经有改变结构，用temp来swap！
1
2
3
4
5
6
class Solution(object):
    def invertTree(self, root):
        if not root:
            return None
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

100. Same Tree

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def isSameTree(self, p, q):
        if not p and not q:
            return True
        elif not p or not q:
            return False
        else:
            return (p.val == q.val and
                   self.isSameTree(p.left, q.left) and
                   self.isSameTree(p.right, q.right))

543. Diameter of Binary Tree

  • DFS + maxDepth
  • postorder to deal with the value returned from left and right subtree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def diameterOfBinaryTree(self, root):
        if not root: return 0

        self.res = 0
        self.maxDepth(root)
        return self.res

    def maxDepth(self, root):
        if not root: return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        self.res = max(self.res, left + right)
        return max(left, right) + 1

222. Count Complete Tree Nodes

  • Time : O($(logn)^2$)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution:
        def countNodes(self, root):
            if not root:
                return 0
            left = self.depth(root.left)
            right = self.depth(root.right)
            if left == right:
                return (2**left) + self.countNodes(root.right)
            else:
                return (2**right) + self.countNodes(root.left)

        def depth(self, root):
            cnt = 0
            while root:
                root = root.left
                cnt += 1
            return cnt
Share