938-二叉搜索樹的范圍和

LiveVideoStack 發布于2019-08-16 13:40 / 2617人閱讀

摘要：前言的第二題二叉搜索樹的范圍和給定二叉搜索樹的根結點，返回和含之間的所有結點的值的和。二叉搜索樹保證具有唯一的值。實現代碼二叉搜索樹的范圍和中序遍歷遞歸

前言

Weekly Contest 110的第二題二叉搜索樹的范圍和：

給定二叉搜索樹的根結點 root，返回 L 和 R（含）之間的所有結點的值的和。
二叉搜索樹保證具有唯一的值。
返回日志的最終順序
示例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
提示：

樹中的結點數量最多為 10000 個。
最終的答案保證小于 2^31。

解題思路

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

實現代碼

    /**
     * 938. 二叉搜索樹的范圍和
     * @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);
        }
    }

GPU云服務器云服務器二叉樹的遍歷二叉樹的存儲二叉樹的存儲結構 java二叉樹的構建

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/72118.html

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

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

HelKyle 2021-11-11 16:55 評論0 收藏0
學習數據結構與算法之二叉搜索樹

摘要：二叉搜索樹是二叉樹的一種，其特征是左側子節點存儲比父節點小的值，右側子節點存儲比父節點大或等于父節點的值。實現和這個兩個方法其實挺簡單的，最小的節點就在二叉搜索樹的最左反之，最大的就在最右。本系列所有文章：第一篇文章：學習數據結構與算法之棧與隊列第二篇文章：學習數據結構與算法之鏈表第三篇文章：學習數據結構與算法之集合第四篇文章：學習數據結構與算法之字典和散列表第五篇文章：學習數據結構...

denson 2019-08-21 11:54 評論0 收藏0
數據結構——樹

摘要：首先，我們了解一下關于樹的基本知識每一個樹都包含一系列的父子關系的節點，每個節點都有一個父節點和若干的子節點零個或者多個沒有父節點的節點稱作是根節點一個節點可以有祖先和后代，子樹由節點和他的后代構成，節點的一個屬性是深度深度就是一個節點祖先首先，我們了解一下關于樹的基本知識：每一個樹都包含一系列的父子關系的節點，每個節點都有一個父節點和若干的子節點（零個或者多個）沒有父節點...

Backache 2019-08-20 14:06 評論0 收藏0
Python數據結構——AVL樹的基本概念

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

jiekechoo 2019-07-24 18:26 評論0 收藏0
數據結構與算法JavaScript （不定時更新）

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

levius 2019-08-26 11:40 評論0 收藏0