[数据结构与算法]938. 二叉搜索树的范围和

题目

938. 二叉搜索树的范围和

思路

二叉树搜索模版题

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} low
 * @param {number} high
 * @return {number}
 */
var rangeSumBST = function(root, low, high) {
	//中序遍历的值的顺序就正好是二叉搜索树的值的顺序
	let queue = [];
	let val = [];
	let sum = 0;
	
	while(root || queue.length){
		while(root){
			queue.push(root);
			root = root.left;
		}
		root = queue.pop();//pop出来
        if (root.val >= low && root.val <= high){
			sum += root.val;
		}//直接判断，符合范围要求则加和
		root = root.right;
	}
    return sum;
};