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

 // 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) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : 
        val(x), left(left), right(right) {}
  };

① bfs

class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        TreeNode* q[12999];
        int res = 0;
        int h = 0, t = 0;
        q[0] = root;
        while(h <= t){
            TreeNode *tmp = q[h ++];
            if(tmp != nullptr){
                int val = tmp -> val;
                if(val >= low && val <= high) res += val;
                if(tmp -> left != nullptr && val >= low) q[++ t] = tmp -> left;
                if(tmp -> right != nullptr && val <= high) q[++ t] = tmp -> right; 
            }
        }       
        return res;
    }
};

② 循环版dfs

class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        stack<TreeNode*> st;
        int res = 0;
        st.push(root);
        while(st.size()){

            TreeNode* tmp = st.top(); st.pop();
            if(tmp != nullptr) {
                int val = tmp -> val;
                if(val >= low && val <= high) res += val;
                if(tmp -> right != nullptr && val <= high) st.push(tmp -> right);
                if(tmp -> left != nullptr && val >= low) st.push(tmp -> left);
            }
        }

        return res;
    }
};

③ 递归

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);
        else if(root -> val < low) return rangeSumBST(root -> right, low, high);
        else return root -> val + 
                    rangeSumBST(root -> left, low, high) + 
                    rangeSumBST(root -> right, low, high);
    }
};

// 因为二叉搜索树的定义 
// 所有左树键值都比根节点小， 右树键值大于等于比根节点键值  
// 由此知: 左树搜索的键值上界是根节点键值
//        右树搜索的键值下界也是根节点的键值
// 所以我们可以把递归的最后一句改为
// 但这样做似乎也没有什么优化可言
root -> val + 
rangeSumBST(root -> left, low, root -> val) + 
rangeSumBST(root -> right, root -> val, high);