【刷算法】二叉搜索樹的第k個結點

plokmju88 發布于2019-08-22 18:48 / 934人閱讀

摘要：題目描述給定一棵二叉搜索樹，請找出其中的第小的結點。例如，，，，，，，中，按結點數值從小到大順序第三小結點的值為。分析二叉搜索樹的特點就是對于某個點來說，左子樹上的點小于該點，右子樹上的點大于該點。

題目描述

給定一棵二叉搜索樹，請找出其中的第k小的結點。例如，（5，3，7，2，4，6，8）中，按結點數值從小到大順序第三小結點的值為4。

分析

二叉搜索樹的特點就是對于某個點來說，左子樹上的點小于該點，右子樹上的點大于該點。所以按照中序遍歷的方法得到的序列即是從小到大的序列。

代碼

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function KthNode(r, k)
{
    if(r === null)
        return null;
    var res = [];
    var s = [];
    var cur = r;
    
    while(cur !== null || s.length !== 0) {
        if(cur !== null){
            s.push(cur);
            cur = cur.left;
        }else{
            cur = s.pop();
            res.push(cur);
            if(res.length === k)
                return res.pop();
            cur = cur.right;
        }
    }
    
    return null;
}

GPU云服務器云服務器二叉樹的遍歷二叉樹的存儲二叉樹求結點個數二叉樹的存儲結構

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

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

?算法入門?《二叉樹 - 二叉搜索樹》簡單05 —— LeetCode 897. 遞增順序搜索樹

文章目錄一、題目1、題目描述2、基礎框架3、原題鏈接二、解題報告1、思路分析2、時間復雜度3、代碼詳解三、本題小知識四、加群須知一、題目 1、題目描述 ??給你一棵二叉搜索樹，請按中序遍歷將其重新排列為一棵遞增順序搜索樹，使樹中最左邊的節點成為樹的根節點，并且每個節點沒有左子節點，只有一個右子節點。??樣例輸入： [5,3,6,2,4,null,8,1,null,null,nu...

Soarkey 2021-09-10 10:51 評論0 收藏0
樹 - （二叉查找樹，紅黑樹，B樹）- BST

摘要：在二叉查找樹上執行基本操作的時間與樹的高度成正比。不同的二叉查找樹可以表示同一組值。紅黑樹樹二叉查找樹，紅黑樹，樹紅黑樹雖是讀書筆記，但是如轉載請注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復制黨關于二叉樹的基本知識，可以參見：Java 實現基本數據結構 2(樹) 以下是算法導論第十二章的學習筆記二叉查找樹 BS...

zhangwang 2019-08-14 12:05 評論0 收藏0
JS數據結構與算法_樹

摘要：上一篇數據結構與算法集合字典一遞歸學習樹離不開遞歸。先序遍歷的一種應用是打印一個結構化的文檔下面的圖描繪了先序遍歷方法的訪問路徑后序遍歷后序遍歷則是先訪問節點的后代節點，再訪問節點本身。上一篇：JS數據結構與算法_集合&字典一、遞歸學習樹離不開遞歸。 1.1 介紹遞歸是一種解決問題的方法，它解決問題的各個小部分，直到解決最初的大問題。遞歸通常涉及函數調用自身。通俗的解釋：年級...

tabalt 2019-08-26 13:35 評論0 收藏0
js數據結構和算法（三）二叉樹

摘要：同樣結點樹的二叉樹，完全二叉樹的深度最小。二叉樹每個結點最多有兩個孩子，所以為它設計一個數據域和兩個指針域是比較自然的想法，我們稱這樣的鏈表叫做二叉鏈表。二叉樹的概念二叉樹（Binary Tree）是n（n>=0）個結點的有限集合，該集合或者為空集（空二叉樹），或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹的二叉樹組成。 showImg(https://seg...

DesGemini 2019-08-21 10:20 評論0 收藏0