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

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. 二叉搜索树中的众数

思路

• 与上一题类似，使用 pre 指针和 cur 指针
• 如果 pre 指针为 null，说明变量的是第一个节点，否则将 pre 更新为上一个节点 pre = cur
• 注意：如果出现频率大于最大值，需要更新最大值，且情况结果数组，说明出现频率更高的元素值

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 的公共祖先？

• 情况一：如果一个节点的左子树出现 p，右子树出现 q，或者右子树出现 p，左子树出现q，那么该节点是 p 和 q 的公共祖先。
• 情况二：节点本身 p(q) 拥有了一个子孙节点 q(p)，那么 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)
};