算法之二叉搜素树范围和

938. 二叉搜索树的范围和 #

给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

解法

1.递归深度优先搜索

按深度优先搜索的顺序计算范围和。记当前子树根节点为 root，分4种情况讨论

root节点为空，返回0
root.val值大于high的值，根据二叉搜索树的性质知道，应该此时去找root的左子树，无需考虑右子树
root.val值小于low的值，根据二叉搜索树的性质知道，应该此时去找root的右子树，无需考虑左子树
root.val值必须在[low, high]范围内

最终应该返回这个节点值和左右子树值的和

1
var rangeSumBST = function(root, low, high) {
2
    if (!root) {
3
        return 0;
4
    }
5
    if (root.val > high) {
6
        return rangeSumBST(root.left, low, high);
7
    }
8
    if (root.val < low) {
9
        return rangeSumBST(root.right, low, high);
10
    }
11
    return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
12
};

2.迭代（广度优先）

使用广度优先搜索的方法，用一个队列 q 存储需要计算的节点。每次取出队首节点时，若节点为空则跳过该节点，否则按方法一中给出的大小关系来决定加入队列的子节点。

1
var rangeSumBST = function(root, low, high) {
2
    let sum = 0;
3
    const q = [root];
4
    while (q.length) {
5
        const node = q.shift();
6
        if (!node) {
7
            continue;
8
        }
9
        if (node.val > high) {
10
            q.push(node.left);
11
        } else if (node.val < low) {
12
            q.push(node.right);
13
        } else {
14
            sum += node.val;
15
            q.push(node.left);
16
            q.push(node.right);
17
        }
18
    }
19
    return sum;
20
};

938. 二叉搜索树的范围和#

938. 二叉搜索树的范围和 #