P225 二叉搜索树的区间和

描述#

这个题目说的是，给你一棵二叉搜索树，以及左右边界 L 和 R，你要将二叉树节点中，大于等于左边界且小于等于右边界的所有节点值都加起来，然后返回这个求和结果。

注意，可以保证二叉搜索树上不存在重复的节点值。

比如说，给你的二叉搜索树是：
 5

/   

2     6
/ \     

1   4     8
给你的左右边界 L 和 R 分别是：
L = 3
R = 6
在这棵二叉搜索树上，位于 3 和 6 之间的节点值有：4，5，6。它们相加等于 15，因此你要返回 15。

代码#

public class AlgoCasts {
  
  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(n)
  public int rangeSumBSTRecursive(TreeNode root, int L, int R) {
    if (root == null) return 0;
    if (root.val < L) return rangeSumBSTRecursive(root.right, L, R);
    if (root.val > R) return rangeSumBSTRecursive(root.left, L, R);
    return root.val +
      rangeSumBSTRecursive(root.left, L, R) +
      rangeSumBSTRecursive(root.right, L, R);
  }

  // Time: O(n), Space: O(n)
  public int rangeSumBSTIterative(TreeNode root, int L, int R) {
    int sum = 0;
    Stack<TreeNode> st = new Stack<>();
    st.push(root);
    while (!st.empty()) {
      TreeNode node = st.pop();
      if (node == null) continue;
      if (node.val < L) st.push(node.right);
      else if (node.val > R) st.push(node.left);
      else {
        sum += node.val;
        st.push(node.left);
        st.push(node.right);
      }
    }
    return sum;
  }

}