溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

LeetCode如何實(shí)現(xiàn)二叉搜索樹(shù)的范圍和

發(fā)布時(shí)間：2021-12-15 10:29:52 來(lái)源：億速云 閱讀：119 作者：小新 欄目：大數(shù)據(jù)

小編給大家分享一下LeetCode如何實(shí)現(xiàn)二叉搜索樹(shù)的范圍和，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！


 

題目描述

給定二叉搜索樹(shù)的根結(jié)點(diǎn) root，返回 L 和 R（含）之間的所有結(jié)點(diǎn)的值的和。

二叉搜索樹(shù)保證具有唯一的值。

示例 1：

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

示例 2：

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

提示：

樹(shù)中的結(jié)點(diǎn)數(shù)量最多為 10000 個(gè)。 最終的答案保證小于 2^31。


 
 
 
 
-------------------機(jī)智的思考線-------------------  
 
 
 
 
-------------------機(jī)智的思考線--------------------  
 
 
 
 
-------------------機(jī)智的思考線-------------------  
 
 
 
 
   

解題方案

 

思路

  • 標(biāo)簽：深度優(yōu)先遍歷

  • 題意：這個(gè)題字面含義很難理解，本意就是求出所有 X >= L 且 X <= R 的值的和

  • 遞歸終止條件：

    • 當(dāng)前節(jié)點(diǎn)為null時(shí)返回0

    • 當(dāng)前節(jié)點(diǎn) X < L 時(shí)則返回右子樹(shù)之和

    • 當(dāng)前節(jié)點(diǎn) X > R 時(shí)則返回左子樹(shù)之和

    • 當(dāng)前節(jié)點(diǎn) X >= L 且 X <= R 時(shí)則返回：當(dāng)前節(jié)點(diǎn)值 + 左子樹(shù)之和 + 右子樹(shù)之和

  • 注意點(diǎn)：通過(guò)判斷X的大小能夠避免遍歷全部樹(shù)的節(jié)點(diǎn)，比如下方的動(dòng)圖中，3這個(gè)值就沒(méi)有必要遍歷

LeetCode如何實(shí)現(xiàn)二叉搜索樹(shù)的范圍和

示例1動(dòng)圖

 
 

代碼

/** * 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);    }}

看完了這篇文章，相信你對(duì)“LeetCode如何實(shí)現(xiàn)二叉搜索樹(shù)的范圍和”有了一定的了解，如果想了解更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！

向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手