案例

GodX...大约 26 分钟

二叉树的最大深度(简)

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

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

示例 1：

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

示例 2：

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

提示：

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

解题思路

方法一：后序遍历

终止条件：当 root 为空，说明已越过叶节点，因此返回深度 0 。
递推工作：本质上是对树做后序遍历。
- 计算节点 root 的左子树的深度，即调用 maxDepth(root.left)。
- 计算节点 root 的右子树的深度，即调用 maxDepth(root.right)。
返回值：返回此树的深度，即 max(maxDepth(root.left), maxDepth(root.right)) + 1

方法二：层序遍历

树的层序遍历 / 广度优先搜索往往利用队列实现。

关键点：每遍历一层，则计数器 +1 ，直到遍历完成，则可得到树的深度。

特例处理：当 root 为空，直接返回深度 0 。
初始化：队列 queue （加入根节点 root ），计数器 res = 0。
循环遍历：当 queue 为空时跳出。
- 初始化一个空列表 tmp ，用于临时存储下一层节点。
- 遍历队列：遍历 queue 中的各节点 node ，并将其左子节点和右子节点加入 tmp。
- 更新队列：执行 queue = tmp ，将下一层节点赋值给 queue。
- 统计层数：执行 res += 1 ，代表层数加 1。
返回值：返回 res 即可。

后序遍历

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

层序遍历

var maxDepth = function (root) {
    if(!root) return 0;
    let res = 0;
    let queue = [];
    queue.push(root);
    while(queue.length) {
        let temp = [];
        for(let node of queue) {
            node.left && temp.push(node.left);
            node.right && temp.push(node.right);
        }
        queue = temp;
        res++
    }
    return res
};

相同的树(简)

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

两棵树上的节点数目都在范围 [0, 100] 内
-104 <= Node.val <= 104

解题思路

终止条件与返回值：

当两棵树的当前节点都为 null 时返回 true
当其中一个为 null 另一个不为 null 时返回 false
当两个都不为空但是值不相等时，返回 false

执行过程：当满足终止条件时进行返回，不满足时分别判断左子树和右子树是否相同，其中要注意代码中的短路效应

时间复杂度：O(n)，n 为树的节点个数。

var isSameTree = function (p, q) {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;
    if (p.val !== q.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};

翻转二叉树(简)

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

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

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100

解题思路

这是一道很经典的二叉树问题。显然，我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转。

var invertTree = function (root) {
    if (!root) return root;
    const left = invertTree(root.left);
    const right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root
};

对称二叉树(简)

给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

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

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

进阶:你可以运用递归和迭代两种方法解决这个问题吗？

递归

var isSymmetric = function (root) {
    return compare(root.left,root.right);
};

function compare(a, b) {
    if(a === null && b === null) return true;
    if(a === null || b === null) return false;
    if (a.val !== b.val) return false;
    return compare(a.left, b.right) && compare(a.right, b.left)
}

迭代

var isSymmetric = function(root) {
    if (!root) return true; // 如果根节点为空，则是对称的

    // 使用栈来模拟递归过程
    const stack = [];
    stack.push(root.left);
    stack.push(root.right);

    while (stack.length > 0) {
        const node1 = stack.pop();
        const node2 = stack.pop();

        // 如果两个节点都为空，继续下一对节点
        if (node1 === null && node2 === null) continue;
        // 如果其中一个节点为空或它们的值不相等，则不是对称的
        if (node1 === null || node2 === null || node1.val !== node2.val) return false;

        // 将下一对节点压入栈中，注意顺序
        stack.push(node1.left);
        stack.push(node2.right);
        stack.push(node1.right);
        stack.push(node2.left);
    }

    // 如果所有节点都匹配，则是对称的
    return true;
};

从前序与中序遍历序列构造二叉树(中)

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列

解题思路

解法一

时间复杂度：O(n^2)，其中 n 为 preorder 的长度。最坏情况下二叉树是一条链，我们需要递归 O(n) 次，每次都需要 O(n) 的时间查找 preorder[0] 和复制数组。
空间复杂度：O(n^2)。

var buildTree = function(preorder, inorder) {
    const n = preorder.length;
    if (n === 0) { // 空节点
        return null;
    }
    const leftSize = inorder.indexOf(preorder[0]); // 左子树的大小
    const pre1 = preorder.slice(1, 1 + leftSize);
    const pre2 = preorder.slice(1 + leftSize);
    const in1 = inorder.slice(0, leftSize);
    const in2 = inorder.slice(1 + leftSize, n);
    const left = buildTree(pre1, in1);
    const right = buildTree(pre2, in2);
    return new TreeNode(preorder[0], left, right);
};

解法二

上面的写法有两个优化点：

用一个哈希表（或者数组）预处理 inorder 每个元素的下标，这样就可以 O(1) 查到 preorder[0] 在 inorder 的位置，从而 O(1) 知道左子树的大小。
把递归参数改成子数组下标区间（左闭右开区间）的左右端点，从而避免复制数组。

var buildTree = function (preorder, inorder, inorderMap = new Map(), preorderStart = 0, inorderStart = 0, n = preorder.length) {
    if (n === 0) { // 空节点
        return null;
    }
    if (!inorderMap.size) { // 只在第一次调用时构建Map
        for (let i = 0; i < inorder.length; i++) {
            inorderMap.set(inorder[i], i);
        }
    }
    const rootValue = preorder[preorderStart]; // 根节点的值
    const rootIndex = inorderMap.get(rootValue); // 根节点在中序遍历中的位置
    const leftSize = rootIndex - inorderStart; // 左子树的大小

    // 构建左子树
    const left = buildTree(preorder, inorder, inorderMap, preorderStart + 1, inorderStart, leftSize);

    // 构建右子树
    const right = buildTree(preorder, inorder, inorderMap, preorderStart + 1 + leftSize, rootIndex + 1, n - leftSize - 1);

    return new TreeNode(rootValue, left, right);
};

从中序与后序遍历序列构造二叉树（中）

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

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

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

提示:

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由不同的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历

解题思路

和上面的从前序与中序遍历序列构造二叉树题目类似，这里就不重复说明了

解法一

var buildTree = function (inorder, postorder) {
    const len = inorder.length;
    if (len === 0) {
        return null
    }
    const leftSize = inorder.indexOf(postorder.at(-1));
    const in1 = inorder.slice(0, leftSize);
    const in2 = inorder.slice(leftSize + 1);
    const pos1 = postorder.slice(0, leftSize);
    const pos2 = postorder.slice(leftSize, in2.length);
    const left = buildTree(in1, pos1);
    const right = buildTree(in2, pos2);
    return new TreeNode(postorder.at(-1), left, right)
};

解法二

var buildTree = function (inorder, postorder, inorderMap = new Map(), inorderStart = 0, inorderEnd = inorder.length) {
    if (inorderEnd === inorderStart) {
        return null;
    }
    if (!inorderMap.size) {
        // 只在第一次调用时构建Map
        for (let i = 0; i < inorder.length; i++) {
            inorderMap.set(inorder[i], i);
        }
    }
    const rootValue = postorder[postorder.length - 1]; // 根节点的值
    const rootIndex = inorderMap.get(rootValue); // 根节点在中序遍历中的位置
    const leftSize = rootIndex - inorderStart; // 左子树的大小

    // 构建左子树
    const left = buildTree(inorder, postorder.slice(0, leftSize), inorderMap, inorderStart, rootIndex);

    // 构建右子树
    const right = buildTree(inorder, postorder.slice(leftSize, postorder.length - 1), inorderMap, rootIndex + 1, inorderEnd);

    return new TreeNode(rootValue, left, right);
};

填充每个节点的下一个右侧节点指针 II(中)

给定一个二叉树：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

示例 1：

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

示例 2：

输入：root = []
输出：[]

提示：

树中的节点数在范围 [0, 6000] 内
-100 <= Node.val <= 100

进阶：

你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序的隐式栈空间不计入额外空间复杂度。

解题思路

BFS

初始化: 如果根节点 root 为空，直接返回 null。否则，将根节点放入一个队列 q 中。
广度优先搜索（BFS）:
- 当队列 q 不为空时，执行以下操作：
  - 创建一个临时数组 tmp，将其赋值为 q 的当前内容，然后清空 q。
  - 遍历 tmp 数组中的每个节点：
    - 如果当前节点 node 不是这一层的第一个节点（即 i 不为 0），则将前一个节点（tmp[i - 1]）的 next 指针指向当前节点 node，从而连接同一层的两个相邻节点。
    - 如果当前节点 node 有左子节点，将左子节点放入队列 q 中。
    - 如果当前节点 node 有右子节点，将右子节点放入队列 q 中。
返回结果：当广度优先搜索完成后，返回根节点 root，此时树中的兄弟节点已经被正确连接。
这个算法通过广度优先搜索的方式，逐层遍历二叉树的节点，并在每层中建立相邻节点之间的连接。通过使用队列来存储每一层的节点，算法能够有效地实现这一目标。

DFS

初始化: 创建一个空数组 pre 用于记录每一层最左边的节点。
深度优先搜索（DFS）:
- 对于每个节点 node 和它所在的深度 depth，执行以下操作：
  - 如果 node 为空，则返回。
  - 如果当前深度 depth 等于 pre 数组的长度，说明 node 是这一层最左边的节点，将其添加到 pre 数组中。
  - 否则，将 pre[depth]（即 node 左边的节点）的 next 指针指向 node，然后将 pre[depth] 更新为 node。
- 递归地对 node 的左子节点和右子节点执行相同的操作，深度增加 1。
开始搜索：从根节点 root 开始，深度为 0，调用 dfs 函数。
返回结果：最后返回根节点 root，此时树中的兄弟节点已经被正确连接。

该算法通过深度优先搜索的方式，巧妙地利用了 pre 数组来记录每一层最左边的节点，从而实现了兄弟节点之间的连接。

BFS

var connect = function (root) {
    if (root === null) {
        return null;
    }
    let q = [root];
    while (q.length) {
        const tmp = q;
        q = [];
        for (let i = 0; i < tmp.length; i++) {
            const node = tmp[i];
            if (i) { // 连接同一层的两个相邻节点
                tmp[i - 1].next = node;
            }
            if (node.left) {
                q.push(node.left);
            }
            if (node.right) {
                q.push(node.right);
            }
        }
    }
    return root;
};

DFS

var connect = function (root) {
    const pre = [];
    function dfs(node, depth) {
        if (node === null) {
            return;
        }
        if (depth === pre.length) { // node 是这一层最左边的节点
            pre.push(node);
        } else { // pre[depth] 是 node 左边的节点
            pre[depth].next = node; // node 左边的节点指向 node
            pre[depth] = node;
        }
        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);
    }
    dfs(root, 0); // 根节点的深度为 0
    return root;
};

二叉树展开为链表(中)

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [0]
输出：[0]

提示：

树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100

**进阶：**你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

解题思路

先用两个变量把原先的左右子树保存起来
将左子树作为右子树(对照下图中第1个树变成第2个树，原来2的左子树3变成了2的右子树3)
将原先的右子树接到当前右子树的末端（看下图第3棵树，5要接到4的下面）

算法流程

递归基础：if (root == null) return; 这行代码是递归的基本情况。如果当前节点 root 是 null，即已经超出了树的结构，那么函数返回。
递归调用：flatten(root.left); 和 flatten(root.right); 这两行代码是对左右子树进行递归调用，将它们拉平。
保存左右子树：let left = root.left; 和 let right = root.right; 这两行代码用于保存当前节点的左右子树，因为在后续操作中会改变 root.left 和 root.right 的值。
拉平当前节点：
- root.left = null; 将当前节点的左子树设置为 null。
- root.right = left; 将当前节点的右子树设置为原来的左子树（现在是一条链表）。
连接原始右子树：while (root.right != null) { root = root.right; } 这行代码用于找到当前节点新的右子树（即原始左子树拉平后的链表）的末端。然后，root.right = right; 将原始的右子树接到这个末端。

这个算法的关键在于它使用了后序遍历的方式（先遍历左右子树，再处理当前节点），这样可以确保在处理当前节点时，其左右子树已经被拉平成链表。通过这种方式，算法能够将整个二叉树转换成一条链表，同时保持了树中节点的相对顺序。

递归

var flatten = function (root) {
  if (root == null) return;

  flatten(root.left);
  flatten(root.right);

  // 1、左右子树已经被拉平成一条链表
  // 先用两个变量把原先的左右子树保存起来
  let left = root.left;
  let right = root.right;

  // 2、将左子树作为右子树
  root.left = null;
  root.right = left;

  // 3、将原先的右子树接到当前右子树的末端
  while (root.right != null) {
    root = root.right;
  }
  root.right = right;
};

迭代

function flatten(root) {
  if (root === null) return;

  let stack = [root]; // 初始化栈，并将根节点压入栈中
  let prev = null; // prev 用于跟踪上一个处理的节点

  // 当栈不为空时，继续处理节点
  while (stack.length > 0) {
    let curr = stack.pop(); // 弹出栈顶元素作为当前处理的节点

    // 如果 prev 不为空，说明我们已经处理过至少一个节点
    // 将 prev 的右子节点设置为 curr，并将 prev 的左子节点设置为 null
    if (prev !== null) {
      prev.left = null;
      prev.right = curr;
    }

    // 保存当前节点的左右子节点
    let left = curr.left;
    let right = curr.right;

    // 如果当前节点有右子节点，将其压入栈中
    if (right !== null) stack.push(right);
    // 如果当前节点有左子节点，将其压入栈中
    if (left !== null) stack.push(left);

    curr.left = null; // 将当前节点的左子节点设置为 null
    prev = curr; // 更新 prev 为当前节点

    // 如果当前节点没有右子节点，且栈中还有节点，将栈顶节点接到当前节点的右子节点上
    if (curr.right === null && stack.length > 0) {
      curr.right = stack[stack.length - 1];
    }
  }
}

路径总和(简)

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

提示：

树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

解题思路

观察要求我们完成的函数，我们可以归纳出它的功能：询问是否存在从当前节点 root 到叶子节点的路径，满足其路径和为 sum。

假定从根节点到当前节点的值之和为 val，我们可以将这个大问题转化为一个小问题：是否存在从当前节点的子节点到叶子的路径，满足其路径和为 sum - val。

不难发现这满足递归的性质，若当前节点就是叶子节点，那么我们直接判断 sum 是否等于 val 即可（因为路径和已经确定，就是当前节点的值，我们只需要判断该路径和是否满足条件）。若当前节点不是叶子节点，我们只需要递归地询问它的子节点是否能满足条件即可。

var hasPathSum = function (root, targetSum) {
    if(root === null) return false;
    targetSum -= root.val;
    if(root.left === root.right) {
        return targetSum === 0;
    }
    return hasPathSum(root.left,targetSum) || hasPathSum(root.right,targetSum)
};

求根节点到叶节点数字之和（中）

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

示例 2：

输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

提示：

树中节点的数目在范围 [1, 1000] 内
0 <= Node.val <= 9
树的深度不超过 10

解题思路

核心思路是使用深度优先搜索（DFS）遍历树的所有路径，并在遍历过程中累加路径值。

算法步骤：

初始化累加器：创建一个变量acc来存储路径数字之和的累加结果。
定义DFS函数：创建一个递归函数dfs，它接受两个参数：当前节点node和当前路径值pre。
递归终止条件：如果当前节点为null，则返回。这是递归的基本终止条件。
更新路径值：将当前节点的值加到pre上，形成新的路径值。这里通过将pre乘以10并加上当前节点的值来实现。
检查叶子节点：如果当前节点是叶子节点（即没有左子节点和右子节点），则将pre加到acc上。这是因为我们到达了一个完整的路径。
递归调用：对当前节点的左右子节点分别调用dfs函数，传递更新后的pre值。
返回结果：在所有递归完成后，返回acc作为最终结果。

var sumNumbers = function (root) {
    let acc = 0;

    function dfs(node, pre) {
        if (node === null) return;

        pre = pre * 10 + node.val; // 更新当前路径值
        if (node.left === null && node.right === null) {
            acc += pre; // 如果是叶子节点，累加路径和
            return; // 叶子节点，无需继续递归
        }
        dfs(node.left, pre); // 递归左子树
        dfs(node.right, pre); // 递归右子树
    }
    dfs(root, 0);
    return acc;
};

二叉树中的最大路径和（难）

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

树中节点数目范围是 [1, 3 * 104]
-1000 <= Node.val <= 1000

解题思路

深度优先搜索（DFS）：算法使用深度优先搜索来遍历二叉树的每个节点。这是一种常用的遍历树的方法，可以确保每个节点都被访问到。
递归计算：对于每个节点，算法递归地计算其左子树和右子树的最大路径和。这是通过递归调用dfs函数实现的。
路径和的选择：在计算每个节点的最大路径和时，算法会考虑两种情况：只包含左子树的路径、只包含右子树的路径，或者同时包含左右子树的路径。这是通过比较左子树和右子树的最大路径和与0的大小来实现的。如果左子树或右子树的最大路径和为负数，则忽略它们，只考虑当前节点的值。
更新全局最大路径和：在计算每个节点的最大路径和时，算法会检查是否需要更新全局最大路径和。这是通过比较当前节点的左子树、右子树和当前节点的值的总和与当前全局最大路径和的大小来实现的。
返回值：dfs函数返回的是经过当前节点的最大路径和。这是通过比较左子树和右子树的最大路径和，然后加上当前节点的值来实现的。
结果：最终，算法返回的是全局最大路径和，这是在遍历整个树的过程中计算得到的。

总的来说，这个算法通过递归地计算每个节点的最大路径和，并更新全局最大路径和，从而找到二叉树中的最大路径和。

var maxPathSum = function (root) {
    let acc = Number.MIN_SAFE_INTEGER; // 初始化全局最大路径和为最小安全整数

    function dfs(node) {
        if (node === null) return 0; // 如果节点为空，返回0

        const left_sum = Math.max(dfs(node.left), 0); // 计算左子树的最大路径和，如果为负则忽略
        const right_sum = Math.max(dfs(node.right), 0); // 计算右子树的最大路径和，如果为负则忽略

        acc = Math.max(left_sum + right_sum + node.val, acc); // 更新全局最大路径和

        return Math.max(left_sum, right_sum) + node.val; // 返回经过当前节点的最大路径和
    }

    dfs(root); // 从根节点开始深度优先搜索
    return acc; // 返回全局最大路径和
};

二叉树的最近公共祖先（中）

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

解题思路

递归基础：检查当前节点是否为 null，或者是否等于 p 或 q。如果是，返回当前节点。这表示如果找到了 p 或 q 中的一个，或者已经到达了树的底部（null），就返回当前节点。
递归遍历：对当前节点的左子节点和右子节点递归调用相同的函数，即 lowestCommonAncestor。这将返回两个值：left 和 right，分别代表左子树和右子树中 p 和 q 的最近公共祖先。
判断最近公共祖先：
- 如果 left 和 right 都不是 null，这意味着 p 和 q 分别位于当前节点的左右子树中，因此当前节点就是它们的最近公共祖先。
- 如果 left 是 null 而 right 不是 null，这意味着 p 和 q 都在右子树中，所以返回 right。
- 如果 right 是 null 而 left 不是 null，这意味着 p 和 q 都在左子树中，所以返回 left。

递归返回：递归调用将返回找到的最近公共祖先，直到达到根节点。

该算法的关键在于它利用了递归的回溯特性，通过比较左右子树的返回值来确定最近公共祖先。它不需要存储整条路径，只需在递归过程中进行比较，这使得算法既高效又简洁。

var lowestCommonAncestor = function (root, p, q) {
    if (root === null || root === p || root === q) {
        return root;
    }
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    if (left && right) {
        return root;
    }
    return left ?? right;
};

二叉树的层平均值（中）

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。

示例 2:

输入：root = [3,9,20,15,7]
输出：[3.00000,14.50000,11.00000]

提示：

树中节点数量在 [1, 104] 范围内
-231 <= Node.val <= 231 - 1

解题思路

这里就说下DFS算法的详细步骤：

定义 dfs 函数，它首先检查当前节点是否为空。如果为空，则返回，不进行任何操作。
检查当前层级 level 是否小于 totals 列表的长度。totals 列表用于存储每一层节点的值之和，而 counts 列表用于存储每一层的节点数量。
如果当前层级小于 totals 列表的长度，说明这一层之前已经访问过，因此只需要更新这一层的总和和节点数量。
如果当前层级等于 totals 列表的长度，说明这是一个新的层级，需要向 totals 和 counts 列表中添加新的元素。
递归调用 dfs 函数，首先访问左子节点，层级加一，然后访问右子节点，层级同样加一。
在递归完成后，通过 zip 函数将 totals 和 counts 列表合并，计算每个层级的平均值，并返回这个平均值列表。

BFS

var averageOfLevels = function (root) {
    let result = [];
    if (!root) return [];
    let queue = [root];
    while (queue.length) {
        const level = [];
        const levelSize = queue.length
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            level.push(node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        const total = level.reduce((a, b) => a + b);
        result.push(total / level.length)
    }
    return result
};

DFS

// 定义一个函数，用于计算每一层的平均值
function averageOfLevels(root) {
    // 初始化两个数组，一个用于存储每一层的总和，一个用于存储每一层的节点数量
    let totals = [];
    let counts = [];

    // 定义一个递归函数，用于深度优先搜索
    function dfs(node, level) {
        // 如果节点为空，返回
        if (!node) return;

        // 如果当前层级小于totals数组的长度，说明这一层之前已经访问过
        if (level < totals.length) {
            // 累加这一层的总和
            totals[level] += node.val;
            // 累加这一层的节点数量
            counts[level] += 1;
        } else {
            // 如果是一个新的层级，添加到totals和counts数组中
            totals.push(node.val);
            counts.push(1);
        }

        // 递归访问左子节点，层级加一
        dfs(node.left, level + 1);
        // 递归访问右子节点，层级加一
        dfs(node.right, level + 1);
    }

    // 从根节点开始，调用dfs函数，起始层级为0
    dfs(root, 0);

    // 通过zip函数将totals和counts数组合并，计算每个层级的平均值
    let result = totals.map((total, index) => total / counts[index]);

    // 返回平均值数组
    return result;
}

昵称

邮箱

网址

按正序
按倒序
按热度

案例

二叉树的最大深度(简)

相同的树(简)

翻转二叉树(简)

对称二叉树(简)

从前序与中序遍历序列构造二叉树(中)

从中序与后序遍历序列构造二叉树（中）

填充每个节点的下一个右侧节点指针 II(中)

二叉树展开为链表(中)

路径总和(简)

求根节点到叶节点数字之和（中）

二叉树中的最大路径和（难）

二叉树的最近公共祖先（中）

二叉树的层平均值（中）

预览: