二叉树与递归 - 深入理解

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    //使用递归
    //归的时候要加自己的深度？

    //boudary
    if(!root) return 0;
    const l = maxDepth(root.left);
    const r = maxDepth(root.right);
    return Math.max(l,r) + 1;
};

/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    /**
     * 核心思路：宏观递归思维
     *
     * 1. 把每个子节点都看作一棵子树的根节点。
     * 2. 相信 minDepth(root) 能返回当前子树的最小深度。
     * 3. 当前层不需要关心子树内部如何计算，
     *    只需要拿到左右子树的结果，再组合出自己的答案。
     */

    // 0. 递归出口：空树没有根节点，深度为 0
    if (root === null) return 0;

    /**
     * 1. 递阶段：向左右子树索取答案
     *
     * 假设递归调用能够正确返回左右子树的最小深度。
     * 注意：0 也是合法答案，表示当前子树为空。
     *
     * 调用栈：
     * - 当前函数执行到递归调用时，会等待子函数返回。
     * - 每次调用都有独立的 root 和局部变量。
     * - 子函数返回后，当前函数才继续向下执行。
     */
    const leftDepth = minDepth(root.left);
    const rightDepth = minDepth(root.right);

    /**
     * 2. 归阶段：根据左右子树的答案，计算当前树的答案
     *
     * 情况一：左子树深度为 0（左子树为空）
     *         只能从右子树寻找叶子节点。
     *
     * 情况二：右子树深度为 0（右子树为空）
     *         只能从左子树寻找叶子节点。
     *
     * 注意：前面已经计算过左右子树的深度，
     *       不要再次调用 minDepth，否则会重复递归。
     */
    if (leftDepth === 0) return rightDepth + 1;
    if (rightDepth === 0) return leftDepth + 1;

    /**
     * 情况三：左右子树都存在
     *         取较小深度，再加上当前根节点这一层。
     *
     * 特殊情况：如果左右子树都为空，说明当前节点是叶子节点。
     *         此时 leftDepth 和 rightDepth 都为 0，
     *         已经被上面的第一个 if 处理，直接返回 1。
     */
    return Math.min(leftDepth, rightDepth) + 1;
};

        1
       / \
      2   3
     /
    4

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumOfLeftLeaves = function(root) {

    // 0. 边界条件：如果不是树了，就返回0
    if(root === null) return 0

    // 1. 递：计算两个子树的左节点值之和
    // 比如站在3的角度，左边9是一个整体，右边20是一个整体，
    let sum = sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right)

    // 需要想清楚，左叶子，其实也相当于整个树以及多个子树的左叶子；如果我站在叶子节点的角度，那我就不知道我是不是叶子节点
    // 所以要在叶子节点的父节点去求和判断
    // 2.1 归：正常树的父节点的话，直接return sum了，
    // 2.2 归：如果root不是正常树，比如是叶子节点，应当返回0；如果是叶子节点的父节点，应当加上左叶子节点
    // 右边叶子节点不需要管
    if(!root.left)  return sum // 如果当前节点连左孩子都没有，那自然不可能存在「以当前节点为父节点的左叶子」，所以不用额外加任何值，直接返回左右子树已经算好的 sum。
    if(root.left.left === null && root.left.right === null) return root.left.val + sum //叶子节点的父节点

    // 想象一下结果来反推：sumOfLeftLeaves（3）= 9 + 15；f(9) = 0; f(20) = 15;
    return sum
};

var hasPathSum = function(root, targetSum) {
    //思路：路径的话，通过递进的时候形成；每次递进减去值；判断答案，归的时候传递true/false
    //节点校验
    if(!root) return false;
    //减去值
    targetSum -= root.val;

    //判断叶子节点和答案
    if(root.left===null && root.right === null){
        return targetSum === 0;
    }
    //值传递
    return hasPathSum(root.left,targetSum) || hasPathSum(root.right,targetSum);
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var goodNodes = function(root) {
    // 思路：dfs遍历，递进维护最大值，归求答案
    let dfs = (root, maxnum) => {
        // 1. 递归出口，如果不是节点，返回0，父级不要+cnt
        if(!root) return 0;
        // 2.1 归：叶子节点，照非叶子节点一样判断就行
        let cnt = root.val >= maxnum ? 1 : 0;
        maxnum = Math.max(maxnum, root.val)

        let leftSum = dfs(root.left, maxnum);
        let rightSum = dfs(root.right, maxnum);

        // 2.2 归：假设两边子节点都返回了子树的好节点个数，那我们直接求和往上归
        return  cnt + leftSum + rightSum
    }
    return dfs(root, -Infinity)
};