题目描述

难度简单127

给定二叉搜索树的根结点 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。

注: 一定要先看清题目,要求出在这颗树中节点数据比L大于等于并且小于等于R值的和;

解法一:递归

原链接:https://leetcode-cn.com/problems/range-sum-of-bst/solution/di-gui-fa-by-jason-2-8/

原文链接:https://leetcode-cn.com/problems/range-sum-of-bst/solution/di-gui-fa-by-jason-2-8/

int rangeSumBST(TreeNode* root, int L, int R) {       if (root == NULL) return 0;             int left_sum = 0,right_sum = 0;     	// R 大于等于 root -> val  说明 二叉搜索树的root -> right 可能有 L 和 R区间的数据       if (root -> val <= R) {            left_sum = rangeSumBST(root -> right,L,R);        }       //L 小于等于 root -> val  说明 二叉搜索树的root -> left 可能有 L 和 R区间的数据        if(root -> val >= L) {            right_sum = rangeSumBST(root -> left,L,R);        }		        int ans = left_sum + right_sum;        //加上这个根节点的数据        if (root -> val >= L && root -> val <= R) {            ans+= root -> val;        }       return ans;    }

时空复杂度分析:

时间复杂度: 为O(N) N为二叉搜索树的节点总数;

空间复杂度: 为O(N);

解法二: 使用stack容器

思路是和解法一相似;

int rangeSumBST(TreeNode* root, int L, int R) {       if (root == NULL) return 0;        stack
   
     temp;        temp.push(root);        int ans = 0;        while(!temp.empty()) {            TreeNode* current = temp.top(); temp.pop();            cout << current -> val << endl;            if (current -> val >= L && current -> val <= R) {                ans += current -> val ;            }            if (current -> val <= R && current -> right) {                temp.push(current -> right);            }            if (current -> val >= L && current -> left) {                temp.push(current -> left);            }        }        return ans;    }

时空复杂度分析:

时间复杂度: 为O(N) N为二叉搜索树的节点总数;

空间复杂度: 为O(N);

解法三:最简化的版本

不使用额外变量:这位老哥对于递归的使用已经非常熟练链接:https://leetcode-cn.com/u/li-zi-he/

int rangeSumBST(TreeNode* root, int L, int R) {        if(root == NULL){            return 0;        }        if(root->val > R){            return rangeSumBST(root->left, L, R);        } else if(root->val < L){            return rangeSumBST(root->right, L, R);        } else {            return root->val + rangeSumBST(root->left, L, R) + rangeSumBST(root->right, L, R);        }    }

时空复杂度分析:

时间复杂度: 为O(N) N为二叉搜索树的节点总数;

空间复杂度: 为O(N);

转载地址：http://jdyki.baihongyu.com/

你可能感兴趣的文章