4.树

1.二叉树的最大深度

方法1：深度优先算法，配合Math.max

var maxDepth = function(root) {
  if (!root) {
    return 0
  } else {
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
  }
};

方法2：广度优先算法，配合while循环，清空当前调用栈，每次进入新的调用栈时则deep+1

function (root) {
  if (!root) return 0

  let stack = [root] // 记录当前层的 tree 节点, 先清空当前层，再进入下一层
  let num = 0 // 记录深度
  // 遍历完 stack
  while(stack.length) {
    num++ // 进入当前层 num+1
    let len = stack.length
    // 清空当前层的调用栈之后，[root1, root2]
    // 将当前的结果 push 进一个新的调用栈 [root3, root4, root5]
    // 再进行下一轮的while循环清空新的调用栈
    for (let i = 0; i < len; i++) {
      let node = stack.shift()
      node.left && stack.push(node.left)
      node.right && stack.push(node.right)
    }
  }
  return num
};