【前言】
今天是力扣打卡第11天！
感謝鐵汁們的陪伴，一起加油鴨！！
在第9天的時候寫過這道題的遞回解題方法，其實DFS使用的解題思想就是遞回，所以大同小異啦，大家簡單看一下純遞回的解法：
https://blog.csdn.net/weixin_57544072/article/details/121196600?spm=1001.2014.3001.5502
原題：二叉搜索樹的范圍和（DFS解法）
題目描述：
給定二叉搜索樹的根結點 root，回傳值位于范圍 [low, high] 之間的所有結點的值的和，
示例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題解 ：
全都在代碼里頭咯，
代碼執行：
/**
* 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;
// //判斷根節點
// if(root->val >= low && root->val <= high){
// result += root->val;
// }
// return result;
//方法二：DFS
//判斷特殊情況
if(root == NULL){
return 0;
}
//如果根節點的值大于high，那么右子樹不滿足，此時只需要判斷左子樹
if(root->val > high){
return rangeSumBST(root->left, low, high);
}
//如果根節點的值小于low，那么左子樹一定不滿足，此時只需要判斷右子樹
if(root->val < low){
return rangeSumBST(root->right, low, high);
}
//否則如果根節點的值在low和high之間，那么三者都需要判斷
return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);
}復雜度分析：
時間復雜度：O(N), 取決于二叉搜索樹的節點數；
空間復雜度：O(N)，取決于遞回呼叫堆疊空間的開銷，
總結：
今天是力扣打卡第11天！
時間很緊，博主和鐵汁們一起堅持，加油！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/355254.html
標籤：其他