leetcode每天5题-Day41（二叉树7-二叉搜索树）

1. 合并二叉树

617. 合并二叉树-简单
b站视频讲解

var mergeTrees = function (root1, root2) {
    const preOrder = (root1, root2) => {
        if(!root1)
            return root2
        if(!root2)
            return root1;
        root1.val += root2.val;
        root1.left = preOrder(root1.left, root2.left);
        root1.right = preOrder(root1.right, root2.right);
        return root1;
    }
    return preOrder(root1, root2);
};
1
2
3
4
5
6
7
8
9
10
11
12
13

2. 二叉搜索树中的搜索

700. 二叉搜索树中的搜索-简单
视频讲解

递归

var searchBST = function(root, val) {
    if(!root) return null;
    if(root.val > val) {
        return searchBST(root.left, val);
    }else if(root.val < val) {
        return searchBST(root.right, val);
    }else{
        return root;
    }    
};
1
2
3
4
5
6
7
8
9
10

迭代

var searchBST = function(root, val) {
    while(root) {
        if(root.val < val) {
            root = root.right;
        }else if(root.val > val) {
            root = root.left;
        }else{
            return root;
        }
    }  
    return null;
};
1
2
3
4
5
6
7
8
9
10
11
12

3. 验证二叉搜索树

98. 验证二叉搜索树-中等
视频讲解

思路：二叉搜索树的一个特性：二叉搜索树的中序遍历是有序的。

误区：递归判断根节点的值大于左节点并小于右节点的值，忽略了左子树的全部节点都要小于根节点，并且右子树的全部节点都要大于根节点。

错误代码示范

// 比如 [5,4,6,null,null,3,7] 该代码就判断错误了
var isValidBST = function(root) {
    if(!root) return true;
    if(root.left && root.left.val >= root.val) return false;
    if(root.right && root.right.val <= root.val) return false;
    return isValidBST(root.left) && isValidBST(root.right);
};
1
2
3
4
5
6
7

最直观的方式是把二叉树转变为数组来判断，但其实也不用转变成数组，可以在递归遍历的过程中直接判断是否有序。

借助数组实现

var isValidBST = function(root) {
    const arr = [];
    const dfs = (root) => {
        if(!root) return true;
        dfs(root.left);
        arr.push(root.val);
        dfs(root.right);
    }
    dfs(root);
    for(let i = 1; i < arr.length; i++) {
        if(arr[i] <= arr[i - 1]) return false;
    }
    return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

递归

思路：与双指针的思路很像，初始化一个空指针pre，pre存放遍历的前一个值，将其与当前值root进行比较。

var isValidBST = function(root) {
    let pre = null;
    const dfs = (root) => {
        if(!root) return true;
        // 注意：要用变量存放遍历左子树与右子树的结果，利用这两个遍历的值做递归的返回值
        let left = dfs(root.left);
        if(pre && pre.val >= root.val) return false;
        pre = root;
        let right = dfs(root.right);
        return left && right;
    }
    return dfs(root);
};
1
2
3
4
5
6
7
8
9
10
11
12
13

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

530. 二叉搜索树的最小绝对差-简单
讲解

借助数组

var getMinimumDifference = function(root) {
    // 最小差值不一定是相邻节点
    let minDiff = Infinity;
    // 借助数组
    const arr = [];
    const dfs = (root) => {
        if(root) {
            dfs(root.left);
            arr.push(root.val);
            dfs(root.right);
        }
    }
    dfs(root);
    for(let i = 1; i < arr.length; i++) {
        let diff = Math.abs(arr[i] - arr[i - 1]);
        minDiff = Math.min(diff, minDiff);
    }
    return minDiff;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

双指针（递归）

思路：用一个pre节点记录一下root节点 即当前节点的前一个节点。在递归过程中更新最小值。

var getMinimumDifference = function(root) {
    // 最小差值不一定是相邻节点
    let pre = null;
    let minDiff = Infinity;
    const dfs = (root) => {
        if(!root) return; 
        //  注意： 这里不需要用变量去接遍历左子树与右子树的值， 因为我们遍历左子树与右子树的目的是更新minDiff的值，在遍历过程中 自然更新了minDiff它的值 最后把minDiff返回就行了
        dfs(root.left);
        if(pre && minDiff > Math.abs(root.val - pre.val)) minDiff = Math.abs(root.val - pre.val);
        pre = root;
        dfs(root.right);
        return minDiff;
        
    }
    return dfs(root);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

⭐迭代法-中序遍历

感觉很绕，自己比较难想出来/难做出来，但理解了之后，觉得思路跟递归很像，只是迭代法用的是while循环。

var getMinimumDifference = function(root) {
    let stack = []
    let cur = root
    let res = Infinity
    let pre = null
    while(cur || stack.length) {
        if(cur) {
            stack.push(cur)
            cur = cur.left
        } else {
            cur = stack.pop()
            if(pre) res = Math.min(res, cur.val - pre.val)
            pre = cur
            cur = cur.right
        }
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5. 二叉搜索树中的众数

501. 二叉搜索树中的众数-简单
讲解

普通二叉树解法

思路：遍历整棵二叉树，用map统计频率，把频率排个序（先把map转成数组再排序），最后取前面高频的元素的集合。

var findMode = function(root) {
    const map = new Map();
    const dfs = (root) => {
        if(!root) return;
        dfs(root.left);
        map.set(root.val, map.has(root.val) ? map.get(root.val) + 1 : 1);
        dfs(root.right);
    }
    dfs(root);
    let arr = Array.from(map), ans = [];
    arr.sort((a,b) => b[1] - a[1]);
    for(let i = 1; i < arr.length; i++) {
        if(arr[i][1] === arr[i - 1][1]) {
            ans.push(arr[i][0]);
        }else{
            break;
        }
    }

    ans.push(arr[0][0]);
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

利用二叉搜索树性质

思路：双指针，一遍遍历二叉搜索树，遍历的同时记录最大频数并更新结果集。

var findMode = function(root) {
    let pre = null, result = [], maxCount = 0, count = 0;
    const dfs = (root) => {
        if(!root) return;
        dfs(root.left);
        if(!pre) {
            count = 1;
        }else if(pre.val === root.val) {
            count++;
        }else {
            count = 1;
        }
        if(count === maxCount) result.push(root.val);

        if(count > maxCount) {
            maxCount = count;
            // 出现更大的次数时  清空之前的结果集
            result = [];
            result.push(root.val);
        }
        pre = root;
        dfs(root.right);
    }
    dfs(root);
    return result;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26