Java教程

938_二叉搜索树的范围和

本文主要是介绍938_二叉搜索树的范围和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

938_二叉搜索树的范围和

 

package 二叉树.二叉搜索树;

import java.awt.HeadlessException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * https://leetcode-cn.com/problems/range-sum-of-bst/
 * 
 * @author Huangyujun
 * 题意是给了一颗 二叉搜素树(有点特殊的树),我这种是通法~啥树都可以
 * 
 */
public class _938_二叉搜索树的范围和 {
    //思路一:遍历(随便一种遍历方式都可以,去比较一下即可了)
    int low = 0;
    int hight = 0;
    int sum = 0;
    public int rangeSumBST(TreeNode root, int low, int high) {
        this.low = low;
        this.hight = high;
        inorder(root);
//        for()到这里又遍历了一次list锁定范围,不快了
        return sum;
    }
    List<Integer> list = new ArrayList<>(); 
    public void inorder(TreeNode root) {
        if(root == null)    return;
        inorder(root.left);
        //拿到当前值
//        list.add(root.val);
        if(root.val >= low && root.val <= hight) {
            sum += root.val;
        }
        inorder(root.right);
    }
    
    //思路二:递归利用二叉搜索树(根大于左子树,根小于右子树)~ 卡在了根在范围内~
    public int rangeSumBST2(TreeNode root, int low, int high) {
        if(root == null) return 0;
        if(root.val < low) {    //只能考虑右子树了
            return rangeSumBST2(root.right, low, high);
        }else if(root.val > high) {    //只能考虑左子树
            return rangeSumBST2(root.left, low, high);
        }    
        //根在范围内的话,(加上 考虑左子树和右子树的情况)~ 递归含义透彻理解:    
        return root.val + rangeSumBST2(root.left, low, high) + rangeSumBST2(root.right, low, high);
    }
    
    //思路三:非递归实现 【队列:当前层的结点一个一个拿出来判断,若当前结点值范围大于high,考虑左子树区域,当前结点值小于low,考虑右子树区域,等于直接累加范围,然后左右子树区域都有可能】
    class Solution2 {
        public int rangeSumBST(TreeNode root, int low, int high) {
            int sum = 0;
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            q.offer(root);
            while (!q.isEmpty()) {
                TreeNode node = q.poll();
                if (node == null) {
                    continue;
                }
                if (node.val > high) {
                    q.offer(node.left);
                } else if (node.val < low) {
                    q.offer(node.right);
                } else {
                    sum += node.val;
                    q.offer(node.left);
                    q.offer(node.right);
                }
            }
            return sum;
        }
    }
}

 

这篇关于938_二叉搜索树的范围和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!