題目

給定一個binary search tree的root node與在樹中的兩個值L與R。
回傳在這棵樹中L到R之間的node的value的總和。
Definition for a binary tree node.

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

Binary search tree

大家應該還記得先前提過的Binary tree。
Binary search tree只是在Binary tree的規則上再加上一條
parent node與 child node的大小關係 是 左<父<右。

解法

採用深度最先搜索(DFS)，並用遞迴的方式。
盡可能一直往左子樹走，不行才往右子樹走。
如果當前node的值小於L，則當前node的左子樹都一定也小於L，就不用繼續往左做。
如果當前node的值大於R，則當前node的右子樹都一定也小於R，就不用繼續往右做。

Code

class Solution {
public:
    int sum = 0;
    int rangeSumBST(TreeNode* root, int L, int R) {
        sum = 0;
        dfs(root,L,R);
        return sum;
    }
    void dfs(TreeNode* curNode, int L, int R){
        if(curNode != NULL){
            if(curNode->val >= L && curNode->val <= R){   
                sum += curNode->val; //範圍內
            }
            if(L < curNode->val){
                dfs(curNode->left, L, R);  //當前節點的值大於L，往左子節點繼續做，反之就不用往左子節點了，因為一定都小於L
            }
            if(curNode->val < R){ //當前節點的值小於R，往右子節點繼續做，反之就不用往右子節點了，因為一定都大於R
                dfs(curNode->right, L, R);
            }
        }
    }
};