530. 二叉搜索樹(shù)的最小絕對(duì)差

思路

• 如果是中序遍歷，那么其遍歷結(jié)果剛好是有序的
• 得到有序數(shù)組，記錄最小差值
• 或者利用前后指針，當(dāng)前節(jié)點(diǎn)與前一節(jié)點(diǎn)依次比較，記錄最小差值

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. 二叉搜索樹(shù)中的眾數(shù)

思路

• 與上一題類(lèi)似，使用 pre 指針和 cur 指針
• 如果 pre 指針為 null，說(shuō)明變量的是第一個(gè)節(jié)點(diǎn)，否則將 pre 更新為上一個(gè)節(jié)點(diǎn) pre = cur
• 注意：如果出現(xiàn)頻率大于最大值，需要更新最大值，且情況結(jié)果數(shù)組，說(shuō)明出現(xiàn)頻率更高的元素值

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++ // 出現(xiàn)相同的元素值，頻率+1
        } else {
            count = 1 // 第一次出現(xiàn)的元素值，頻率為1
        }
        if (count === maxCount) {
            res.push(cur.val)
        }
        if (count > maxCount) {// 如果計(jì)數(shù)大于最大值
            maxCount = count // 更新最大頻率
            res = []
            res.push(cur.val)
        }
        pre = cur
        getMaxCount(cur.right)
    }
    getMaxCount(root)
    return res
};

236. 二叉樹(shù)的最近公共祖先

思路

如何判斷一個(gè)節(jié)點(diǎn)是節(jié)點(diǎn) p 和 節(jié)點(diǎn) q 的公共祖先？

• 情況一：如果一個(gè)節(jié)點(diǎn)的左子樹(shù)出現(xiàn) p，右子樹(shù)出現(xiàn) q，或者右子樹(shù)出現(xiàn) p，左子樹(shù)出現(xiàn)q，那么該節(jié)點(diǎn)是 p 和 q 的公共祖先。
• 情況二：節(jié)點(diǎn)本身 p(q) 擁有了一個(gè)子孫節(jié)點(diǎn) q(p)，那么 p 或 q 本身就是公共祖先。

var lowestCommonAncestor = function(root, p, q) {
    // 判斷某一個(gè)節(jié)點(diǎn)左子樹(shù)是否出現(xiàn)過(guò)p（q），右子樹(shù)是否出現(xiàn)過(guò)q（p）
    const travelTree = function(root,p,q) {
        // 遞歸結(jié)束條件 找到了p或者q，或者都沒(méi)有找到
        if (root === p || root === q || root === null) {
            return root
        }
        let left = travelTree(root.left, p, q)
        let right = travelTree(root.right, p, q)
        // 遞歸結(jié)束返回最終結(jié)果
        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)
};