LeetCode如何實現二叉搜索樹的范圍和

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

我們提供的服務有：成都網站制作、做網站、微信公眾號開發、網站優化、網站認證、高臺ssl等。為超過千家企事業單位解決了網站和推廣的問題。提供周到的售前咨詢和貼心的售后服務，是有科學管理、有技術的高臺網站制作公司

題目描述

給定二叉搜索樹的根結點 root，返回 L 和 R（含）之間的所有結點的值的和。

二叉搜索樹保證具有唯一的值。

示例 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

提示：

樹中的結點數量最多為 10000 個。最終的答案保證小于 2^31。

-------------------機智的思考線-------------------

-------------------機智的思考線--------------------

-------------------機智的思考線-------------------

解題方案

思路

標簽：深度優先遍歷
題意：這個題字面含義很難理解，本意就是求出所有 X >= L 且 X <= R 的值的和
遞歸終止條件：

當前節點為null時返回0
當前節點 X < L 時則返回右子樹之和
當前節點 X > R 時則返回左子樹之和
當前節點 X >= L 且 X <= R 時則返回：當前節點值 + 左子樹之和 + 右子樹之和

注意點：通過判斷X的大小能夠避免遍歷全部樹的節點，比如下方的動圖中，3這個值就沒有必要遍歷

LeetCode如何實現二叉搜索樹的范圍和

示例1動圖

代碼

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

看完了這篇文章，相信你對“LeetCode如何實現二叉搜索樹的范圍和”有了一定的了解，如果想了解更多相關知識，歡迎關注創新互聯行業資訊頻道，感謝各位的閱讀！

本文名稱：LeetCode如何實現二叉搜索樹的范圍和
文章網址：http://m.newbst.com/article4/jescoe.html

成都網站建設公司_創新互聯，為您提供響應式網站、營銷型網站建設、品牌網站建設、微信小程序、自適應網站、App設計