package week02;

import java.util.ArrayList;

import java.util.List;

/**

* @创建人 luoxiang

* @创建时间 2019/6/14 17:54

* @描述 LeetCode : 938. 二叉搜索树的范围和 https://leetcode-cn.com/problems/range-sum-of-bst/

*/

public class RangeSumBst938 {

public static void main(String[] args) {

TreeNode node = new TreeNode(10);

node.left = new TreeNode(5);

node.right = new TreeNode(15);

node.left.left = new TreeNode(3);

node.left.right = new TreeNode(7);

node.right.right = new TreeNode(18);

System.out.println(new RangeSumBst938().rangeSumBST2(node, 7, 15));

}

/**

* Method 1 : 中序遍历 ， 然后在 有序集合中 计算和 ；当前 值 大于 R ,直接break,避免无效的循环；

* 时间复杂度 : O(N) ; 中序遍历 + 循环

* 空间复杂度 : O(N) ; list 集合

*/

public int rangeSumBST(TreeNode root, int L, int R) {

List<Integer> list = new ArrayList<>();

inOrder(root, list);

int sum = 0;

for (int i = 0; i < list.size(); i++) {

if (L <= list.get(i) && list.get(i) <= R)

sum += list.get(i);

if (list.get(i) > R) break;

}

return sum;

}

private void inOrder(TreeNode root, List<Integer> list) {

if (root == null) return;

inOrder(root.left, list);

list.add(root.val);

inOrder(root.right, list);

}

/**

* Method 2 : DFS 使用 二叉搜索树的特性， 在递归中操作；

* L 的值大于当前根节点的值时，从根的右子树中找

* R 的值小于当前根节点的值时，从根的左子树中找

* 不然都要找

* 时间复杂度 : O(N) ;

* 空间复杂度 : O(N) ;

*/

public int rangeSumBST2(TreeNode root, int L, int R) {

if(root==null) return 0;

if(root.val<L) return rangeSumBST2(root.right,L,R);

if(root.val>R) return rangeSumBST2(root.left,L,R);

return root.val+rangeSumBST2(root.right,L,R)+rangeSumBST2(root.left,L,R);

}

}