資訊專欄INFORMATION COLUMN
摘要：大家簡單看一下純遞歸的解法原題二叉搜索樹的范圍和解法題目描述給定二叉搜索樹的根結(jié)點，返回值位于范圍之間的所有結(jié)點的值的和。
【前言】
今天是力扣打卡第11天！
感謝鐵汁們的陪伴，一起加油鴨?。?/p>
在第9天的時候?qū)戇^這道題的遞歸解題方法，其實DFS使用的解題思想就是遞歸，所以大同小異啦。大家簡單看一下純遞歸的解法：
https://blog.csdn.net/weixin_57544072/article/details/121196600?spm=1001.2014.3001.5502
題目描述：
給定二叉搜索樹的根結(jié)點?root，返回值位于范圍?[low, high]?之間的所有結(jié)點的值的和。?
示例1：
?
?
輸入：root = [10,5,15,3,7,null,18], low = 7, high = 15輸出：32示例2：
輸入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10輸出：23題解 ：
全都在代碼里頭咯。
代碼執(zhí)行：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */int rangeSumBST(struct TreeNode* root, int low, int high){ // //方法一：遞歸法 // //找邊界 // if(root == NULL){ // return 0; // } // //左子樹 // int leftSum = rangeSumBST(root->left, low, high); // //右子樹 // int rightSum = rangeSumBST(root->right, low, high); // int result = leftSum + rightSum; // //判斷根節(jié)點 // if(root->val >= low && root->val <= high){ // result += root->val; // } // return result; //方法二：DFS //判斷特殊情況 if(root == NULL){ return 0; } //如果根節(jié)點的值大于high，那么右子樹不滿足，此時只需要判斷左子樹 if(root->val > high){ return rangeSumBST(root->left, low, high); } //如果根節(jié)點的值小于low，那么左子樹一定不滿足，此時只需要判斷右子樹 if(root->val < low){ return rangeSumBST(root->right, low, high); } //否則如果根節(jié)點的值在low和high之間，那么三者都需要判斷 return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);}復(fù)雜度分析：
時間復(fù)雜度：O(N),?取決于二叉搜索樹的節(jié)點數(shù)；
空間復(fù)雜度：O(N)，取決于遞歸調(diào)用棧空間的開銷。
總結(jié)：
今天是力扣打卡第11天！
時間很緊，博主和鐵汁們一起堅持，加油??！?
?
?
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/123049.html
摘要：前言今天是力扣打卡第天天天做遞歸做煩了，換換腦子，嘿嘿。原題不用加減乘除做加法題目描述寫一個函數(shù)，求兩個整數(shù)之和，要求在函數(shù)體內(nèi)不得使用四則運算符號。補(bǔ)碼的優(yōu)勢加法減法可以統(tǒng)一處理只有加法器。 【前言】 今天是力扣打卡第15天！ 天天做遞歸做煩了，換換腦子，嘿嘿。 原題： 不用加減...
摘要：有效三角形的個數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個數(shù)字?？偨Y(jié)本題和三數(shù)之和很像，都是三個數(shù)加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸，所以空間復(fù)雜度為 ...
摘要：前言今天是刷題打卡第天可能有鐵汁會問，為什么變成刷好題，而不是刷了呢因為最近筆者遇到很多經(jīng)典的筆試題，想著記錄下來，方便大家和自己學(xué)習(xí)，所以今后筆者會在標(biāo)題上注明是不是力扣題。 【前言】 今天是刷題打卡第21天！ 可能有鐵汁會問，為什么變成刷好題， 而不是刷LeetCode 了呢？因為...
題目地址：https://leetcode-cn.com/probl...題目描述： 給定一個非空二叉樹，返回其最大路徑和。 本題中，路徑被定義為一條從樹中任意節(jié)點出發(fā)，達(dá)到任意節(jié)點的序列。該路徑至少包含一個節(jié)點，且不一定經(jīng)過根節(jié)點。 示例 1: 輸入: [1,2,3] 1 / 2 3 輸出: 6 示例 2: 輸入: [-10,9,20,nul...
閱讀 1391·2021-11-22 09:34
閱讀 2592·2021-11-12 10:36
閱讀 1128·2021-11-11 16:55
閱讀 2343·2020-06-22 14:43
閱讀 1478·2019-08-30 15:55
閱讀 1992·2019-08-30 15:53
閱讀 1776·2019-08-30 10:50
閱讀 1234·2019-08-29 12:15
