Day 21 | 530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数、236.二叉树的最近公共祖先

Leetcode 530.二叉搜索树的最小绝对差

题目：530.二叉搜索树的最小绝对差

初始思路

题目给的很特殊，是个二叉搜索树，根据昨天的98.验证二叉搜索树可以知道，可以把二叉搜索树转变成一个有序递增的数组，然后在这个数组上求差值。

代码

var getMinimumDifference = function (root) {
    let arr = []
    const buildArr = (root) => {
        if (root) {
            buildArr(root.left)
            arr.push(root.val)
            buildArr(root.right)
        }
    }
    buildArr(root)
    // arr数组是逐渐递增的
    let min = arr[arr.length - 1]
    for (let i = 1; i < arr.length; i++){
        if (min > arr[i] - arr[i - 1]){
            min = arr[i] - arr[i - 1]
        }
    }
    return min
};

感想

1. 果然和我想的一样~利用了二叉搜索树的有序性。
2. 在遍历数组的时候，我们已知了数组是非递减的，可以确定差值就存在相邻的两个元素之间，所以遍历的时候两个相减就可以了。

Leetcode 501.二叉搜索树中的众数

题目：501.二叉搜索树中的众数

初始思路

按照上题的思路，进行遍历获得arr，然后映射到map上，统计出现最多的字符。

代码

var findMode = function (root) {
    // 使用辅助map
    let map = new Map()
    // 递归
    const traverTree = (root) => {
        if (!root) return
        traverTree(root.left)
        let count = map.has(root.val) ? map.get(root.val) + 1 : 1
        map.set(root.val, count)
        traverTree(root.right)
    }
    traverTree(root)
    let max = map.get(root.val)
    // 因为不一定只有一个众数，所以返回一个数组
    let res = []
    for (let [key, value] of map) {
        // 如果当前值等于最大出现次数就在res增加
        if (value === max) {
            res.push(key)
        }
        // 如果value的值大于原本的maxCount就清空res的所有值，因为找到了更大的
        if (value > max) {
            res = []
            max = value
            res.push(key)
        }
    }
    return res
};

var findMode = function (root) {
    // 不使用额外空间，使用中序遍历,设置出现最大次数初始值为1
    let count = 0, maxCount = 1;
    let pre = root, res = [];
    // 1.确定递归函数及函数参数
    const travelTree = function (cur) {
        // 2. 确定递归终止条件
        if (cur == null) {
            return;
        }
        travelTree(cur.left);
        // 3. 单层递归逻辑
        if (pre.val === cur.val) {
            count++;
        } else {
            count = 1;
        }
        pre = cur;
        if (count === maxCount) {
            res.push(cur.val);
        }
        if (count > maxCount) {
            res = [];
            maxCount = count;
            res.push(cur.val);
        }
        travelTree(cur.right);
    }
    travelTree(root);
    return res;
};

感想

1. 思路一样，但是在进行比较最大值的时候要灵活使用map，同时res是一个数组，不是一个数。
2. 不使用map的没咋看懂。

Leetcode 236.二叉树的最近公共祖先

题目：236.二叉树的最近公共祖先 讲解：https://www.bilibili.com/video/BV1jd4y1B7E2

初始思路

没啥思路

代码

var lowestCommonAncestor = function (root, p, q) {
    // 后序遍历
    const travelTree = (root, p, q) => {
        if (root == null || root === p || root === q) {
            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)
};

感想

1. 视频讲解很清晰，把思路看懂之后代码就可以看明白了。通过后序遍历实现回溯，如果在子树中匹配到了p或者q，就向祖先返回这个值，如果左右子树都返回了非空值，说明这个点就是公共祖先。
2. 图示
   
3. 原来已经打卡20天了吗，真快啊！什么时候能拿到offer呢。