Weekly Contest 110的第二题 二叉搜索树的范围和:数组
给定二叉搜索树的根结点
root
,返回L
和R
(含)之间的全部结点的值的和。日志二叉搜索树保证具备惟一的值。code
返回日志的最终顺序递归
示例1:leetcode
输入:root = [10,5,15,3,7,null,18], L = 7, R = 15 输出:32示例2:get
输入:root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10 输出:23提示:test
- 树中的结点数量最多为
10000
个。- 最终的答案保证小于
2^31
。
本题我选择了一个笨方法去完成,就是利用二叉搜索树的一个特性:经过中序遍历二叉搜索树后能够获得一个递增的有序序列。因此我选择了中序遍历二叉搜索树得到递增且有序的数组,而后遍历数组获取须要的数组元素进行累加。List
/** * 938. 二叉搜索树的范围和 * @param root * @param L * @param R * @return */ public int rangeSumBST(TreeNode root, int L, int R) { List<Integer> list=new ArrayList<Integer>(); int result=0; if(root!=null){ inorderTraversal(root,list); } for(int i:list){ if(i>=L && i<=R){ result+=i; } } return result; } /** * 中序遍历(递归) * @param root * @param list */ private void inorderTraversal(TreeNode root,List<Integer> list){ if(root.left==null && root.right==null){ list.add(root.val); }else if(root.left==null && root.right!=null){ list.add(root.val); inorderTraversal(root.right,list); }else if(root.left!=null && root.right==null){ inorderTraversal(root.left,list); list.add(root.val); }else{ inorderTraversal(root.left,list); list.add(root.val); inorderTraversal(root.right,list); } }