LeetCode.938-範圍内求二叉搜尋樹節點值之和(Range Sum of BST)

這是悅樂書的第359次更新，第386篇原創

01 看題和準備

今天介紹的是LeetCode算法題中Easy級别的第221題（順位題号是938）。給定二叉搜尋樹的根節點，傳回節點值在[L,R]之間的所有節點的值的總和。二叉搜尋樹的節點值唯一。例如：

輸入：root = [10,5,15,3,7，null，18]，L = 7，R = 15

輸出：32

輸入：root = [10,5,15,3,7,13,18,1，null，6]，L = 6，R = 10

輸出：23

注意：

• 樹中的節點數最多為10000。
• 最終答案保證不到2^31。

02 第一種解法

既然給的是二叉搜尋樹，那麼周遊節點我們就選取中序周遊的方式，這樣最直接，存入

List

中，然後周遊

List

中的節點值，将節點值大于等于

L

且小于等于

R

的進行累加，最後傳回

sum

即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rangeSumBST(TreeNode root, int L, int R) {
        List<Integer> list = new ArrayList<Integer>();
        helper(root, list);
        int sum = 0;
        for (Integer num : list) {
            if (num >= L && num <= R) {
                sum += num;
            }
        }
        return sum;
    }

    public void helper(TreeNode root, List<Integer> list){
        if (root == null) {
            return ;
        }
        helper(root.left, list);
        list.add(root.val);
        helper(root.right, list);
    }
}
           

03 第二種解法

針對第一種解法，我們也可以使用疊代的方式來實作，借助棧。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rangeSumBST(TreeNode root, int L, int R) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode tem = stack.pop();
            if (tem != null) {
                list.add(tem.val);
            }
            if (tem != null && tem.left != null) {
                stack.push(tem.left);
            }
            if (tem != null && tem.right != null) {
                stack.push(tem.right);
            }
        }
        int sum = 0;
        for (Integer num : list) {
            if (num >= L && num <= R) {
                sum += num;
            }
        }
        return sum;
    }
}
           

04 第三種解法

我們其實不用将節點值存起來後再統一處理，直接在周遊節點的時候，将在

[L,R]

範圍内的節點值累加即可，最後傳回

sum

。此解法是疊代的方式。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rangeSumBST(TreeNode root, int L, int R) {
        int sum = 0;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode tem = stack.pop();
            if (tem != null) {
                if (tem.val >= L && tem.val <= R) {
                    sum += tem.val;
                }
            }
            if (tem != null && tem.left != null) {
                stack.push(tem.left);
            }
            if (tem != null && tem.right != null) {
                stack.push(tem.right);
            }
        }
        return sum;
    }
}
           

05 第四種解法

針對第三種解法，我們也可以使用遞歸的方式。定義一個全局變量

sum

，依舊使用中序周遊的方式，将在

[L,R]

範圍内的節點值累加，最後傳回

sum

。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private Integer sum = 0;

    public int rangeSumBST(TreeNode root, int L, int R) {
        if (root == null) {
            return sum;
        }        
        rangeSumBST(root.left, L, R);
        if (root.val >= L && root.val <= R) {
            sum += root.val;
        }
        rangeSumBST(root.right, L, R);
        return sum;
    }
}
           

06 第五種解法

針對第四種解法，我們也可以不使用全局變量，借助二叉搜尋樹節點值按照左根右的大小排列特性，如果目前節點值比

L

小，就往右邊找，如果比

R

大，就往左邊找，最後求和。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public int rangeSumBST(TreeNode root, int L, int R) {
        if (root == null) {
            return 0;
        }
        if (root.val < L) {
            return rangeSumBST(root.right, L, R);
        }
        if (root.val > R) {
            return rangeSumBST(root.left, L, R);
        }
        return root.val + rangeSumBST(root.left, L, R) + 
                rangeSumBST(root.right, L, R);
    }
}
           

07 小結

算法專題目前已連續日更超過七個月，算法題文章227+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！