代码随想录训练营Day21 | 530.二叉搜索树的最小绝对差,

2023-10-31  本文已影响0人  是小张啊啊
530. 二叉搜索树的最小绝对差
思路
var getMinimumDifference = function(root) {
    if (!root) {
        return 0
    }
    let result = Number.MAX_SAFE_INTEGER
    let res = []
    const getDiff = (root) => {
        if(!root) {
            return
        }
        getDiff(root.left)
        res.push(root.val)
        if (res.length > 1) {
            result = Math.min(result, Math.abs(res[res.length - 1] - res[res.length - 2]))
        }
        getDiff(root.right)
    }
    getDiff(root)
    return result
};
var getMinimumDifference = function(root) {
    let result = Number.MAX_SAFE_INTEGER
    let pre = null
    const getDiff = (cur) => {
        if (!cur) {
            return
        }
        getDiff(cur.left)
        if(pre) {
            result = Math.min(result, Math.abs(pre.val - cur.val))
        }
        pre = cur
        getDiff(cur.right)
    }
    getDiff(root)
    return result
};
501. 二叉搜索树中的众数
思路
var findMode = function(root) {
    let res = []
    let count = 1
    let pre = null
    let maxCount = 0
    const getMaxCount = (cur) => {
        if(!cur) {
            return
        }
        getMaxCount(cur.left)
        // 处理逻辑
        if (!pre) {
            count = 1 // 频率为1
        } else if (pre.val === cur.val) {
            count++ // 出现相同的元素值,频率+1
        } else {
            count = 1 // 第一次出现的元素值,频率为1
        }
        if (count === maxCount) {
            res.push(cur.val)
        }
        if (count > maxCount) {// 如果计数大于最大值
            maxCount = count // 更新最大频率
            res = []
            res.push(cur.val)
        }
        pre = cur
        getMaxCount(cur.right)
    }
    getMaxCount(root)
    return res
};
236. 二叉树的最近公共祖先
思路

如何判断一个节点是节点 p 和 节点 q 的公共祖先?

var lowestCommonAncestor = function(root, p, q) {
    // 判断某一个节点左子树是否出现过p(q),右子树是否出现过q(p)
    const travelTree = function(root,p,q) {
        // 递归结束条件 找到了p或者q,或者都没有找到
        if (root === p || root === q || root === null) {
            return root
        }
        let left = travelTree(root.left, p, q)
        let right = travelTree(root.right, p, q)
        // 递归结束返回最终结果
        if (left !== null && right !== null) {
            return root
        }
        if (left === null && right !== null) {
            return right
        } else if (left !== null && right === null) {
            return left
        } else {
            return null
        }
    }
    return travelTree(root, p, q)
};
上一篇 下一篇

猜你喜欢

热点阅读