[leetcode] 二叉树最大高度

示例：
设计算法求给定二叉树的最大告诉，如下图二叉树返回的最大高度是3

最容易想到的是可以类似树的层序遍历，我们可以使用广度优先算法遍历树的每一层，level递增，直到最后一层。
广度优先搜索：为从起点开始由近及远进行广泛的搜索。

// BFS
function maxDepth(root: TreeNode | null): number {
  let level = 0
  let stack = []
  stack.push(root)
  while (stack.length) {
    let size = stack.length
    for (let i = 1; i <= size; i++) {
      if (i === 1) level += 1
      const node = stack.shift()
      if (node.left) stack.push(node.left)
      if (node.right) stack.push(node.right)
    }
  }
  return level
};

这个比较容易想到没什么难度，但还有一种解法是利用递归：

说下怎么想到递归的：将问题拆分成一个个子问题，树的最大深度，就是左右子树的深度的最大值加1，而树的末端节点也刚好符合这个规律，因为末端节点左右子树深度都为0，max(0, 0) + 1 = 1，所以求二叉树最大高度可以看作子问题的重复，可以用递归。代码如下：

//  递归
function maxDepth(root: TreeNode | null): number {
  if (root == null) {
    return 0;
  } else {
    let leftHeight = maxDepth(root.left);
    let rightHeight = maxDepth(root.right);
    return Math.max(leftHeight, rightHeight) + 1;
  }
}