Day01

算法每日一题

原题链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=problem-list-v2&envId=2cktkvj
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    let ans = null; // 用于存储最低公共祖先节点
    // 定义一个深度优先搜索函数
    const dfs = (root) => {
        if (root === null) return false; // 如果当前节点为空，返回 false

        // 递归遍历左子树
        const l = dfs(root.left);
        // 递归遍历右子树
        const r = dfs(root.right);

        // 如果左子树和右子树都找到了 p 或 q，或者当前节点是 p 或 q 且左子树或右子树也找到了 p 或 q
        if ((l && r) || ((root.val === p.val || root.val === q.val) && (l || r))) {
            ans = root; // 当前节点就是最低公共祖先
        }
        // 返回当前节点是否是 p 或 q，或者左子树或右子树是否找到了 p 或 q
        return l || r || (root.val === p.val || root.val === q.val);
    }
    // 从根节点开始执行深度优先搜索
    dfs(root);
    // 返回最低公共祖先节点
    return ans;
};

在解决二叉树问题时，递归是一种常用且有效的方法。面对二叉树，不要被其复杂的结构迷惑。可以将左子树和右子树分别看作一个整体，然后将问题拆分成更小的子问题来解决。

在寻找二叉树的最近公共祖先（Lowest Common Ancestor, LCA）时，我们需要注意以下几点：

特殊情况：
如果当前节点是 p 或 q，那么当前节点就是最近公共祖先之一。此时，只需检查另一个节点是否在当前节点的子树中即可。这种情况的条件是：(root.val = p.val || root.val = q.val) && (l || r)。

一般情况：
如果当前节点不是 p 或 q，则需要检查 p 和 q 是否分别位于当前节点的左右子树中。我们考虑一个问题：pq可能同时存在于左子树或者同时存在于右子树吗，答案显然是不可能的，如果同时存在于左子树，那root.left节点肯定是比当前节点更靠近pq节点的，右子树同理，最近公共祖先节点肯定不是当前节点。所以，如果 p 和 q 分别位于当前节点的左右子树中，那么当前节点就是最近公共祖先。这种情况的条件是：p 在左子树中，q 在右子树中，或反之。

前端学习记录

webpack入门
Webpack 是一个用于 JavaScript 文件打包的工具，支持多种模式和配置。它主要分为开发模式和生产模式：

开发模式：
开发模式下，Webpack 会生成包含注释和未压缩的代码，以便于调试。
打包后的代码量通常比生产模式多，因为包含了开发工具和调试信息。

生产模式：
生产模式下，Webpack 会进行代码压缩和优化，以减少文件体积和提高性能。
打包后的代码量通常较小，适合部署到生产环境。

注意需要自己建package.json文件，并且name字段的值不能为webpack

npm init // 快速生成package.json