938 range sum of BST

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. 视频讲解

4. 总结

注意递归的基准情况

938 range sum of BST

原文：https://www.cnblogs.com/MartinTai/p/14669359.html