Recursion on Tree

Q: for each node in a tree, store the number of nodes in its left child subtree

• way of thinking:

1. what do you expect from your leaf child/ right child?
   total number of nodes in my left subtree
   total number of nodes in my right subtree
2. what do you want to do in the current layer?
   store the number of nodes in the left subtree
3. what do you want to return to your parent?
   same as number 1

def chang_subtree(node):
  if node is None:
    return 0
  left_total = change_subtree(node.left)
  right_total = change_subtree(node.right)
  node.total_left = left_total
  return 1 + left_total + right+total

Q: Find the node with the max difference in the total number of descendents in its left subtree and right subtree.

• way of thinking:

1. what do you expect from your leaf child/ right child?
   total number of nodes in my left subtree
   total number of nodes in my right subtree
2. what do you want to do in the current layer?
   diff = abs(left_total - right_total)
   global_max_diff = max(diff, global_max_diff)
3. what do you want to return to your parent?
   return 1 + left_total + right_total

global_max = -1
res = None

def node_diff(root):
  if root is None:
    return 0
  left_total = node_diff(root.left)
  right_total = node_diff(root.right)
  global global_max
  global res
  if abs(left_total - right_total) > global_max:
    global_max = abs(left_total - right_total)
    res = root
  return left_total + right_total + 1

Generally, choose root is None as base case. But sometimes, if we need something related to leaf, we need to choose leaf node( root.left is None and root.rightis None) as base case.

Q: Given a binary tree, find its minimum depth.

def minHeight(root):
  if root is None: #edge case
    return 0
  if root.left is None and root.right is None #base case
    return 1
#此處必須選他作為base case否則只有一個(gè)孩子的node會(huì)返回0
  left = minHeight(root.left) if root.left else float('inf') #infinity
  right = minHeight(root.right) if root.right else float('inf')
  return min(left, right) + 1

Q: Given a binary tree, write a function to determine whether this tree is a binary search tree

def BST(root): #這個(gè)function在這里有g(shù)lobal的意味
  if root is None:
    return True
  min = float('-inf')
  max = float('inf')
  return isBST(root, min, max)

def isBST(root, min, max): #check the order of the values in the tree
  if root is None:
    return True
  if roo.val <= min or root.val >= max:
    return False
  return isBST(root.left, min, root.val) and isBST(root.right, root.val, max)

other ideas
a. use inorder traversal

#儲(chǔ)存當(dāng)前上一個(gè)節(jié)點(diǎn)的value到prev中弊予，看它是不是比當(dāng)前value小。對(duì)于root症革，prev node是left始鱼， 對(duì)于right仔掸，prev node是root。所以recursion中先找left医清，執(zhí)行inorder left起暮，存入prev，比較它與當(dāng)前value会烙，然后存當(dāng)前value于prev中负懦，執(zhí)行inorder right
def is ValidBST(root):
  prev = [None]
  res = [True]
  inorder(root, prev, res)
  return res[0]
def inorder(root, prev, res):
  if not root:
    return
  inorder(root.left, prev, res)
  if prev[0] and prev[0] >= root.val:
    res[0] = False
  prev[0] = root.val
  inorder(root.right, prev, res)

b.

• way of thinking:

1. what do you expect from your leaf child/ right child?
   left_res: 左子樹是否為BST/左子樹最大值/左子樹最小值
   right_res: 右子樹是否為BST/右子樹最大值/右子樹最小值
2. what do you want to do in the current layer?
   isBST = left_res.isBST and right_res.isBST and lef_res.max < root.val and right_res.min > root.val
3. what do you want to return to your parent?
   return (isBST, left_res.min or root.val, right_res.max or root.val)

# in python: 12 or 25 = 12
#                  12 and 25 = 25
# if 25 == if True 和c++用法相同

def isBSTHelper(root):
  if not root:
    return (True, None, None)
  left_res = isBSTHelper(root.left)
  right_res = isBSTHelper(root.right)
  if not left_res[0] or not right_res[0]:
    return (False, None, None)
  if left_res[2] and root.val <= left_res[2]:
    return (False, None, None)
  if right_res[1] and root.val >= right.res[1]:
    return (False, None, None)
  return (True, left_res[1] or root.val, right_res[2] or root.val)

Q: Find the lowest Common Children

• way of thinking:

1. what do you expect from your leaf child/ right child?
   LCA found in the children
2. what do you want to do in the current layer?
   case 1: LCA found in both cases -> current root is LCA
   case 2: LCA found ar one side of children -> LCA found in the children
3. what do you want to return to your parent?
   LCA found in the children

def LCA(root, p, q)
  if not root:
    return None
  if root == p or root == q:
    return root
  left_res = LCA(root.left, p, q)
  right_res = LCA(root.right, p, q)
  if left_LCA and right_LCA:
    return root
  else if left_res:
    return left_res
  else:
    return right_res