重启DAY6 二叉树与递归

跟着灵茶山艾府大佬学习算法思路的day6，目标是在一个月内掌握hot100

b站链接如下：

看到递归就晕？带你理解递归的本质！【基础算法精讲 09】

二叉树的最大深度 题目描述：

给定一个二叉树 root ，返回其最大深度。

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

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

提示：

• 树中节点的数量在 [0, 104] 区间内。
• -100 <= Node.val <= 100

思路：

这道题目主要是关于递归的思考：

灵神的经验是不要一上来就陷入二叉树的细节，先将二叉树简化

如果子问题与原问题相似，且需要子问题不断把计算结果返回给上一级问题，就适合用递归实现

把问题不断分解（递），总会有一个尽头，即递归的边界条件（归）

第二种方法：在递归时除了可以将底部节点往上传递，也可以将路径上的节点个数传下去：

在递归的同时还可以维护一个全局变量，每次加完1之后就更新全局变量的最大值。

代码：

普通递归自底向上：

var maxDepth = function(root) {
    if (!root) return 0;
    
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);
    
    return Math.max(leftDepth, rightDepth) + 1; // 算上根节点，所以+1
};

维护全局变量自顶向下：

var maxDepth = function(root) {
    let ans = 0;
    function dfs(node, depth) {
        if (node === null) {
            return;
        }
        depth++;
        ans = Math.max(ans, depth);
        dfs(node.left, depth);
        dfs(node.right, depth);
    };
    dfs(root, 0);
    return ans;
};

总结：

两种方法的时间空间复杂度均为o(n)。