题目
leetcode938：二叉搜寻树的范畴和
给定二叉搜寻树的根结点 root，返回值位于范畴 [low, high] 之间的所有结点的值的和。
//树结构public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() { } TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }}//办法体public class Solution { public int rangeSumBST(TreeNode root, int low, int high) { }}思路
看到树这种无关的构造，首先想到就是深度优先或者广度优先，明天先用深度优先解这题。
深度优先模板
算法是有迹可循的，比方深度优先，实现根本用递归。
//万能递归模板 private void recursion(TreeNode root) { if(root == null) { return; } //解决逻辑在这里 前序遍历 recursion(root.right); //解决逻辑在这里 中序遍历 recursion(root.left); //解决逻辑在这里 后序遍历 }做题前先写下这个模板，这个就是深度优先遍历一颗树。具体题目，采纳其中摸一种遍历模式，而后做适当的形变即可。
做题
public int rangeSumBST(TreeNode root, int low, int high) { }输出一个树，low，high，求树中处于low，high之间的和。
ok，咱们先写模板
public int rangeSumBST(TreeNode root, int low, int high) { if(root == null) { return 0; } rangeSumBST(root.right, low, high); rangeSumBST(root.left, low, high); }root是一个二叉搜寻树，排好序了的树，能够对root.val退出判断解决逻辑
public int rangeSumBST(TreeNode root, int low, int high) { if (root == null) { return 0; } if (root.val < low) { } else if (root.val > high) { } else { } rangeSumBST(root.right, low, high); rangeSumBST(root.left, low, high); }如果根节点小于low，右边就能够全副舍弃
如果根节点大于high，左边就能够全副舍弃
如果根节点在low，high两头，那么就是左子树的值加上右子树的值加上根节点的值
最终变形为
public int rangeSumBST(TreeNode root, int low, int high) { if (root == null) { return 0; } if (root.val < low) { return rangeSumBST(root.right, low, high); } else if (root.val > high) { return rangeSumBST(root.left, low, high); } else { return rangeSumBST(root.right, low, high) + rangeSumBST(root.left, low, high) + root.val; } }