Recursion & Tree

• 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要的值要一样就接上了！！

# 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

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.

# 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)

# 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的！！！

# 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

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.