当前位置 博文首页 > 数据结构和算法：LeetCode 938. 二叉搜索树的范围和
截止到目前我已经写了 500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
关于二叉树的前中后，以及BFS遍历可以看下《373，数据结构-6,树》
关于二叉树的Morris遍历方式可以看下《488，二叉树的Morris中序和前序遍历》
解法比较多，这里就随便挑一个来写，比如二叉树的中序遍历递归写法如下
public void inOrderTraversal(TreeNode node) {
if (node == null)
return;
inOrderTraversal(node.left);
System.out.println(node.val);
inOrderTraversal(node.right);
}
我们来对他改造一下，遍历每个节点的时候判断他的值
int res = 0;
public int rangeSumBST(TreeNode root, int low, int high) {
inOrderTraversal(root, low, high);
return res;
}
public void inOrderTraversal(TreeNode node, int low, int high) {
if (node == null)
return;
inOrderTraversal(node.left, low, high);
//如果当前节点的值在[low, high]之间，就累加
if (node.val >= low && node.val <= high)
res += node.val;
inOrderTraversal(node.right, low, high);
}
public int rangeSumBST(TreeNode root, int low, int high) {
//递归边界条件判断
if (root == null)
return 0;
//当前节点以及他的右子树的值都太大了，不要了
if (root.val > high) {
return rangeSumBST(root.left, low, high);
}
//当前节点以及他的左子树的值都太小了，也不要了
if (root.val < low) {
return rangeSumBST(root.right, low, high);
}
//如果当前节点值在[low, high]之间，就留下
return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
}
