938-二叉搜索樹(shù)的范圍和

LiveVideoStack 發(fā)布于2019-08-16 13:40 / 2624人閱讀

摘要：前言的第二題二叉搜索樹(shù)的范圍和給定二叉搜索樹(shù)的根結(jié)點(diǎn)，返回和含之間的所有結(jié)點(diǎn)的值的和。二叉搜索樹(shù)保證具有唯一的值。實(shí)現(xiàn)代碼二叉搜索樹(shù)的范圍和中序遍歷遞歸

前言

Weekly Contest 110的第二題二叉搜索樹(shù)的范圍和：

給定二叉搜索樹(shù)的根結(jié)點(diǎn) root，返回 L 和 R（含）之間的所有結(jié)點(diǎn)的值的和。
二叉搜索樹(shù)保證具有唯一的值。
返回日志的最終順序
示例1：
輸入：root = [10,5,15,3,7,null,18], L = 7, R = 15
輸出：32
示例2：
輸入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
輸出：23
提示：

樹(shù)中的結(jié)點(diǎn)數(shù)量最多為 10000 個(gè)。
最終的答案保證小于 2^31。

解題思路

本題我選擇了一個(gè)笨方法去完成，就是利用二叉搜索樹(shù)的一個(gè)特性：通過(guò)中序遍歷二叉搜索樹(shù)后可以得到一個(gè)遞增的有序序列。所以我選擇了中序遍歷二叉搜索樹(shù)獲得遞增且有序的數(shù)組，然后遍歷數(shù)組獲取需要的數(shù)組元素進(jìn)行累加。

實(shí)現(xiàn)代碼

    /**
     * 938. 二叉搜索樹(shù)的范圍和
     * @param root
     * @param L
     * @param R
     * @return
     */
    public int rangeSumBST(TreeNode root, int L, int R) {
        List list=new ArrayList();
        int result=0;
        if(root!=null){
            inorderTraversal(root,list);
        }
        for(int i:list){
            if(i>=L && i<=R){
                result+=i;
            }
        }
        return result;
    }

    /**
     * 中序遍歷(遞歸)
     * @param root
     * @param list
     */
    private void inorderTraversal(TreeNode root,List list){
        if(root.left==null && root.right==null){
            list.add(root.val);
        }else if(root.left==null && root.right!=null){
            list.add(root.val);
            inorderTraversal(root.right,list);
        }else if(root.left!=null && root.right==null){
            inorderTraversal(root.left,list);
            list.add(root.val);
        }else{
            inorderTraversal(root.left,list);
            list.add(root.val);
            inorderTraversal(root.right,list);
        }
    }

云服務(wù)器 GPU云服務(wù)器二叉樹(shù)的遍歷二叉樹(shù)的存儲(chǔ) 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) java二叉樹(shù)的構(gòu)建

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/72118.html

相關(guān)文章

【手把手帶你刷LeetCode】——11.二叉搜索樹(shù)的范圍和（DFS）

摘要：大家簡(jiǎn)單看一下純遞歸的解法原題二叉搜索樹(shù)的范圍和解法題目描述給定二叉搜索樹(shù)的根結(jié)點(diǎn)，返回值位于范圍之間的所有結(jié)點(diǎn)的值的和。【前言】今天是力扣打卡第11天！感謝鐵汁們的陪伴，一起加油鴨?。? 在第9天的時(shí)候?qū)戇^(guò)這道題的遞歸解題方法，其實(shí)DFS使用的解題思想就是遞歸，所以大同小異啦...

HelKyle 2021-11-11 16:55 評(píng)論0 收藏0
學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之二叉搜索樹(shù)

摘要：二叉搜索樹(shù)是二叉樹(shù)的一種，其特征是左側(cè)子節(jié)點(diǎn)存儲(chǔ)比父節(jié)點(diǎn)小的值，右側(cè)子節(jié)點(diǎn)存儲(chǔ)比父節(jié)點(diǎn)大或等于父節(jié)點(diǎn)的值。實(shí)現(xiàn)和這個(gè)兩個(gè)方法其實(shí)挺簡(jiǎn)單的，最小的節(jié)點(diǎn)就在二叉搜索樹(shù)的最左反之，最大的就在最右。本系列所有文章：第一篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊(duì)列第二篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之鏈表第三篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之集合第四篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之字典和散列表第五篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)...

denson 2019-08-21 11:54 評(píng)論0 收藏0
數(shù)據(jù)結(jié)構(gòu)——樹(shù)

摘要：首先，我們了解一下關(guān)于樹(shù)的基本知識(shí)每一個(gè)樹(shù)都包含一系列的父子關(guān)系的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有一個(gè)父節(jié)點(diǎn)和若干的子節(jié)點(diǎn)零個(gè)或者多個(gè)沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)稱作是根節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)可以有祖先和后代，子樹(shù)由節(jié)點(diǎn)和他的后代構(gòu)成，節(jié)點(diǎn)的一個(gè)屬性是深度深度就是一個(gè)節(jié)點(diǎn)祖先首先，我們了解一下關(guān)于樹(shù)的基本知識(shí)：每一個(gè)樹(shù)都包含一系列的父子關(guān)系的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有一個(gè)父節(jié)點(diǎn)和若干的子節(jié)點(diǎn)（零個(gè) 或者多個(gè)）沒(méi)有父節(jié)點(diǎn)...

Backache 2019-08-20 14:06 評(píng)論0 收藏0
Python數(shù)據(jù)結(jié)構(gòu)——AVL樹(shù)的基本概念

摘要：我們知道，當(dāng)樹(shù)變得不平衡時(shí)和操作會(huì)使二叉搜索樹(shù)的性能降低到。樹(shù)實(shí)現(xiàn)抽象數(shù)據(jù)類型就像一個(gè)普通的二叉搜索樹(shù)，唯一不同的是這棵樹(shù)的工作方式。我們通過(guò)比較每個(gè)節(jié)點(diǎn)的左右子樹(shù)的高度完成比較。平衡二叉搜索樹(shù) 在上一節(jié)中我們討論了建立一個(gè)二叉搜索樹(shù)。我們知道，當(dāng)樹(shù)變得不平衡時(shí)get和put操作會(huì)使二叉搜索樹(shù)的性能降低到O(n)。在這一節(jié)中我們將看到一種特殊的二叉搜索樹(shù)，它可以自動(dòng)進(jìn)行調(diào)整，以確保樹(shù)...

jiekechoo 2019-07-24 18:26 評(píng)論0 收藏0
數(shù)據(jù)結(jié)構(gòu)與算法JavaScript （不定時(shí)更新）

摘要：每個(gè)列表中的數(shù)據(jù)項(xiàng)稱為元素。棧被稱為一種后入先出，的數(shù)據(jù)結(jié)構(gòu)。散列使用的數(shù)據(jù)結(jié)構(gòu)叫做散列表。不包含任何成員的集合稱為空集，全集則是包含一切可能成員的集合。因此二叉搜索樹(shù)需要平衡，即左右子樹(shù)高度要相近。樓樓非計(jì)算機(jī)專業(yè)，但是對(duì)計(jì)算機(jī)也還算喜歡。個(gè)人理解若有偏差，歡迎各位批評(píng)指正！對(duì)于數(shù)據(jù)結(jié)構(gòu)和算法一直是我的薄弱環(huán)節(jié)，相信大多數(shù)前端工程師可能多少會(huì)有些這方面的弱點(diǎn)，加上數(shù)據(jù)結(jié)構(gòu)和算法本...

levius 2019-08-26 11:40 評(píng)論0 收藏0