leetcode.938. 二叉搜索树的范围和

r囧r小猫 2023-01-17 06:26 68阅读 0赞

# leetcode.938. 二叉搜索树的范围和 #

# 深度优先搜索-官方 #

class Solution { 
    public:
        int rangeSumBST(TreeNode *root, int low, int high) { 
            if (root == nullptr) { 
                return 0;
            }
            if (root->val > high) { 
                return rangeSumBST(root->left, low, high);
            }
            if (root->val < low) { 
                return rangeSumBST(root->right, low, high);
            }
            return root->val + rangeSumBST(root->left, low, high) 
            + rangeSumBST(root->right, low, high);
        }
    };

# 广度优先搜索-官方 #

class Solution { 
    public:
        int rangeSumBST(TreeNode *root, int low, int high) { 
            int sum = 0;
            queue<TreeNode*> q({ root});
            while (!q.empty()) { 
                auto node = q.front();
                q.pop();
                if (node == nullptr) { 
                    continue;
                }
                if (node->val > high) { 
                    q.push(node->left);
                } else if (node->val < low) { 
                    q.push(node->right);
                } else { 
                    sum += node->val;
                    q.push(node->left);
                    q.push(node->right);
                }
            }
            return sum;
        }
    };

# 中序遍历 #

#include <iostream>
    #include <vector>
    #include <stack>
    
    using namespace std;
    
    struct TreeNode { 
    	int val;
    	TreeNode* left;
    	TreeNode* right;
    	TreeNode() : val(0), left(nullptr), right(nullptr) { }
    	TreeNode(int x) : val(x), left(nullptr), right(nullptr) { }
    	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) { }
    };
    
    
    class Solution { 
    private:
    	void ptree(TreeNode* node,vector<int> &vec) { 
    		if (node == nullptr) { 
    			return;
    		}
    		if (node->left != nullptr)ptree(node->left, vec);
    		//cout << node->val << endl;
    		vec.push_back(node->val);
    		if (node->right != nullptr)ptree(node->right, vec);
    	}
    public:
    	
    	int rangeSumBST(TreeNode* root, int low, int high) { 
    		vector<int> vec;
    		ptree(root,vec);
    		//cout << " " << endl;
    		int sum = 0;
    		for (auto i : vec)
    		{ 
    			//cout << i << endl;
    			if (i >= low && i <= high)sum += i;
    		}
    		return sum;
    	}
    };
    
    int main()
    { 
    	TreeNode* tr1 = new TreeNode(10);
    	TreeNode* tr2 = new TreeNode(5);
    	TreeNode* tr3 = new TreeNode(15);
    	TreeNode* tr4 = new TreeNode(3);
    	TreeNode* tr5 = new TreeNode(7);
    	TreeNode* tr6 = new TreeNode(18);
    
    	tr1->left = tr2;
    	tr1->right = tr3;
    	tr2->left = tr4;
    	tr2->right = tr5;
    	tr3->right = tr6;
    
    	Solution s;
    	cout << s.rangeSumBST(tr1, 7, 15) << endl;
    
    	return 0;
    }