二叉树的最大深度

题目介绍.gif

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

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

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

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

示例

返回它的最大深度 3

测试数据:

    var node = {
      val: 1,
      left: {
        val: 2,
        right: {
          val: 3,
        },
      },
      right: {
        val: 2,
      },
    };

我想到的解法.gif

这是一个平庸的正向思维解法

    var maxDepth = function(root) {
      let count = 0;
      function able(node, depth) {
        if (!node) {
          return depth;
        }
        if (node.left) {
          able(node.left, depth + 1);
        } else {
          if (count < depth) {
            count = depth;
          }
        }

        if (node.right) {
          able(node.right, depth + 1);
        } else {
          if (count < depth) {
            count = depth;
          }
        }
      }
      able(root, 1);
      return count;
    };

吐槽一下，函数名叫maxDepth搞得我count变量想了好久要叫什么名字...

业务中这样的解法已经够用了，不过还是能简练点
合并了当left、right没有时的操作，确实是一样的，这里可以仔细想一想

    var maxDepth = function(root) {
      let count = 0;
      function able(node, depth) {
        if (!node) return;

        count = Math.max(count, depth);
        node.left && able(node.left, depth + 1);
        node.right && able(node.right, depth + 1);
      }
      able(root, 1);
      return count;
    };

有木有觉得able这个函数很碍眼，我一开始时想着直接用maxDepth递归，可是他没给我传第二个参数，在形参上和在函数内部可大不相同

其实，我们可以转换个思维，前面只关注了往下的方向，其实往上的方向也可以被掌控

 if (!node) return;

改成

 if (!node) return 0;

也就是每向上返回一次加1

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

这才是代码简练的正确打开方式，性能上差别体现不出来的。

完