[LeetCode]Range Sum of BST

很直接的recursion的问题，分几种情况:

• 当前node值小于L，那么我们只需要看右子树
• 当前node值大于R，那么我们只需要看左子树
• 否则，我们两个子树都需要继续递归

时间复杂度O(k)，k为在L和R之间的节点数量，代码如下:

	class Solution {
	public:
	int rangeSumBST(TreeNode* root, int L, int R) {
	if (!root)return 0;
	if (root->val < L)return rangeSumBST(root->right, L, R);
	else if (root->val > R)return rangeSumBST(root->left, L, R);
	else return root->val + rangeSumBST(root->left, L, R) + rangeSumBST(root->right, L, R);
	}
	};

view raw Range Sum of BST.cpp hosted with ❤ by GitHub