1. 题目描述

在符合给定范围内的二叉搜索树的节点的值进行累加。

本质上也是二叉树的遍历。

2. 题解

全局变量的递归解法

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

真正意义上的递归

class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if (!root)
            return 0;
        else if (root->val < low)
            return rangeSumBST(root->right, low, high);
        else if (root->val > high)
            return rangeSumBST(root->left, low, high);
        // roo->val belong to [low,high]
        return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);
    }
};

3. 视频讲解

<iframe frameborder="no" scrolling="no" src="//player.bilibili.com/player.html?aid=544900956&bvid=BV1Ti4y1N7FX&cid=321101095&page=1&as_wide=1&high_quality=1&danmaku=0" style="position: absolute; width: 100%; height: 100%; left: 0; top: 0"></iframe>

4. 总结

注意递归的基准情况