今日学习

二叉搜索树的最小绝对差

题目链接/文章讲解：https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.html

视频讲解：https://www.bilibili.com/video/BV1DD4y11779

第一想法

根据二叉搜索树的特点，最小绝对差一定出现在相邻的元素中，所以只用构建数组，然后两两相减即可

/**
 * 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 getMinimumDifference = function (root) {
    let arr = []
    var buildarr = function (root) {
        if (root) {
            buildarr(root.left)
            arr.push(root.val)
            buildarr(root.right)
        }
        return arr
    }
    buildarr(root)
    let res = Infinity
    for (let i = 1; i < arr.length; i++) {
        res = Math.min(res, arr[i] - arr[i - 1])
    }
    return res
};

二叉搜索树中的众数

https://programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html

视频讲解：https://www.bilibili.com/video/BV1fD4y117gp

第一想法

先遍历搜索树，然后用map找到众数

/**
 * 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 findMode = function (root) {
    let arr = []
    var buildarr = function (root) {
        if (root) {
            buildarr(root.left)
            arr.push(root.val)
            buildarr(root.right)
        }
        return arr
    }
    buildarr(root)
    const map = new Map()

    for (const i of arr) {
        map.set(i, (map.get(i) || 0) + 1)
    }

    let maxCount = 0;
    for (const count of map.values()) {
        maxCount = Math.max(maxCount, count);
    }

    // 找出所有出现次数等于最大次数的元素
    const result = [];
    for (const [key, value] of map) {
        if (value === maxCount) {
            result.push(key);
        }
    }
    return result
};

二叉树的最近公共祖先

https://programmercarl.com/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html

视频讲解：https://www.bilibili.com/video/BV1jd4y1B7E2

今日学习

第一想法

从下向上递归！

/**
 * 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) {
    var tranversal = function (root, p, q) {
        if (root == null || root === p || root === q) return root

        let left = tranversal(root.left,p,q)
        let right = tranversal(root.right,p,q)
        if(left !== null && right !== null) return root
        else if(left === null && right !== null) return right
        else if(left !== null && right === null) return left
        else return null
    }
    return tranversal(root, p, q);
    
};