26 - 二叉树的最大深度

题目

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：

给定二叉树 [3,9,20,null,null,15,7]，

3 / 9 20 / 15 7

返回它的最大深度 3 。

解答

递归

root的深度，等于左节点的深度，和右节点的深度，取个最大值。因此不断往下递归即可。

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

Runtime: 72 ms, faster than 21.18% of JavaScript online submissions forMaximum Depth of Binary Tree.

Memory Usage: 36.9 MB, less than 80.68% of JavaScript online submissions for Maximum Depth of Binary Tree.

更过分的是看到了一行代码的解决方案。。

https://leetcode.com/problems/maximum-depth-of-binary-tree/discuss/149214/JS

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

Runtime: 60 ms, faster than 81.42% of JavaScript online submissions forMaximum Depth of Binary Tree.

Memory Usage: 37.2 MB, less than 24.68% of JavaScript online submissions for Maximum Depth of Binary Tree.

看到了一种，又写了个方法来递归

var maxDepth = function(root) {
  return getDepth(root, 0)
}

var getDepth = function(node, depth) {
  if (!node) {
    return depth;
  }
  return Math.max(getDepth(node.right, depth + 1), getDepth(node.left, depth + 1))
}

Runtime: 68 ms, faster than 37.93% of JavaScript online submissions forMaximum Depth of Binary Tree.

Memory Usage: 36.9 MB, less than 82.79% of JavaScript online submissions for Maximum Depth of Binary Tree.

迭代

深度优先搜索，记录每个节点向下延伸的深度，取最大值。

var maxDepth = function(root) {
  let depth = 0;
  if (!root) {
    return depth;
  }
  let stack = [root];
  let cur_depth = 1;
  while (stack.length > 0) {
    let cur = stack.pop();
    depth = Math.max(depth, cur_depth);
    if (cur) {
      cur_depth++;
      stack.push(cur.left);
      cur_depth--;
      stack.push(cur.right);
    }
  }
  return depth;
};

差不多是这个意思，但这个是解不出来的，我还要研究下。。