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