【刷算法】二叉搜索树的第k个结点

plokmju88 发布于2019-08-22 18:48 / 850人阅读

摘要：题目描述给定一棵二叉搜索树，请找出其中的第小的结点。例如，，，，，，，中，按结点数值从小到大顺序第三小结点的值为。分析二叉搜索树的特点就是对于某个点来说，左子树上的点小于该点，右子树上的点大于该点。

题目描述

给定一棵二叉搜索树，请找出其中的第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;
}

私有云超融合服务器二叉树的遍历二叉树的存储二叉树求结点个数二叉树的存储结构

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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