一：解题思路
方法一：递归法 Time:O(n),Space:O(n)
方法二：迭代法 Time:O(n),Space:O(n)
二：完整代码示例 (C++版和Java版)
方法一C++:
class Solution { public: int rangeSumBST(TreeNode* root, int L, int R) { if (root == NULL) return 0; if (root->val < L) return rangeSumBST(root->right,L,R); if (root->val > R) return rangeSumBST(root->left,L,R); return root->val + rangeSumBST(root->left, L, R) + rangeSumBST(root->right,L,R); } };
方法一Java:
class Solution { public int rangeSumBST(TreeNode root, int L, int R) { if(root==null) return 0; if(root.val<L) return rangeSumBST(root.right,L,R); if(root.val>R) return rangeSumBST(root.left,L,R); return root.val+rangeSumBST(root.left,L,R)+rangeSumBST(root.right,L,R); } }
方法二C++:
class Solution { public: int rangeSumBST(TreeNode* root, int L, int R) { if (root == NULL) return 0; int sum = 0; stack<TreeNode*> s; s.push(root); while (!s.empty()) { TreeNode* node = s.top(); s.pop(); if (node == NULL) continue; if (node->val < L) s.push(node->right); else if (node->val > R) s.push(node->left); else { sum += node->val; s.push(node->left); s.push(node->right); } } return sum; } };
方法二Java:
class Solution { public int rangeSumBST(TreeNode root, int L, int R) { if(root==null) return 0; int sum=0; Stack<TreeNode> s=new Stack<>(); s.push(root); while (!s.empty()) { TreeNode node=s.pop(); if(node==null) continue; if(node.val<L) s.push(node.right); else if(node.val>R) s.push(node.left); else { sum+=node.val; s.push(node.left); s.push(node.right); } } return sum; } }
原文：https://www.cnblogs.com/repinkply/p/12725021.html