题解 | #农场牛的最佳观赏区间#
农场牛的最佳观赏区间
https://www.nowcoder.com/practice/7b49f5ad9814424d8c41de44f671d59e
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 *二叉搜索树的中序遍历为递增序列,按照中序遍历判断是否在区间内,返回累加值,如果节点值大于区间最大值直接返回(递增序列后续val 都比最大值大) * * @param root TreeNode类 * @param low int整型 * @param high int整型 * @return int整型 */ public int rangeSumBST (TreeNode root, int low, int high) { int sum = 0; Stack<TreeNode> stack = new Stack<>(); while (!stack.isEmpty() || root != null) { if (null != root) { stack.push(root); root = root.left; } else { TreeNode node = stack.pop(); if (node.val >= low && node.val <= high) { sum += node.val; } if (node.val > high) { return sum; } root = node.right; } } return sum; } }