SwordFaith's Blog

Enlighten our memory

0%

LeetCode 938 C++非递归解

发表于 分类于

执行用时：112ms 击败 100% 的 C++ 提交

内存消耗：37.9mb 击败 100% 的 C++ 提交

题目

给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。
二叉搜索树保证具有唯一的值。

示例 1：

输入：root = [10,5,15,3,7,null,18], L = 7, R = 15
输出：32

示例 2：

输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10

输出：23  

提示：

  1. 树中的结点数量最多为 10000 个。
  2. 最终的答案保证小于 2^31。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/range-sum-of-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

因为输入为二叉搜索树，因此中序遍历即为有序数组，变成顺序加和问题。

递归法可直接递归中序遍历，并返回加和值，能搜索到很多解。

迭代法可以降低递归调用开销，但需要注意的是一定要破坏重入条件，以我的方法为例，如果不修改已经访问过的节点对应左子树，会在重新访问根节点时，重新进入左子树，形成死循环。

还看到一种不推荐的暴力方法是层序遍历，并将符合条件的值加和，没有利用性质，应该会比较慢。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int rangeSumBST(TreeNode* root, int L, int R) {
        if (root == NULL) return 0;
        
        stack<TreeNode*> pstack; // 迭代栈
        pstack.push(root);
        
        int ans = 0;
        
        while( !pstack.empty() ) {
            TreeNode* pa=pstack.top();
            if (pa->left != NULL) {
                pstack.push(pa->left);
                pa->left = NULL; // 防止退回后重入
            } else {
                //ordered_tree.push_back(pa->val);
                if(pa->val >= L) {
                    if (pa->val > R) break;
                    else ans += pa->val;
                }
                pstack.pop();
                if (pa->right != NULL) {
                    pstack.push(pa->right);
                }
            }
        }
        
        return ans;
    }
};