二叉搜索树中第k小的元素

weblog 609 0 0

leetcode230题(中等

原链接:https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/submissions/

问题描述

给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。

示例1

输入:root = [3,1,4,null,2], k = 1
输出:1

示例2

输入:root = [5,3,6,2,4,null,null,1], k = 3
输出:3

解题思路

递归中序遍历二叉搜索树,因为这种遍历方式是有序的,且顺序是从大到小。当遍历到第k个元素时返回当前节点的val值就可以了。

代码(java)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        this.k=k;
        dfs(root);
        return val;
    }
    int k;
    int i=1;
    int val;
    boolean b=false;
    public void dfs(TreeNode root){
        if(b||root==null){
            return;
        }
        dfs(root.left);
        if(!b&&i==k){
            val=root.val;
            b=true;
            return;
        }
        i++;
        dfs(root.right);
    }
}

测试结果

 

猜你喜欢
official 662 和一个head为一个节点链表。如果在,存在一条一直向下路径,且每个点数值恰好一一对应以head为首链表每个节点值,那么请你返回True,否则返回False。一直向下路径意思
weblog 3884 什么是前驱节点和后继节点?某节点前驱节点val值于该节点val值并且值是最大那个节点。某节点后继节点val值大于该节点val值并且值是最那个节点。下面给出一个节点类
official 639 径。说明:叶子节点是指没有子节点节点。示例:输入:1/\23\5输出:["1-2-5","1-3"]解释:所有根节点到叶子节点路径为:1-2-5,1-3解题思路递归得方式遍历(深度优先),
official 586 leetcode110题(简单)原链接https://leetcode-cn.com/problems/balanced-binary-tree/题目描述给定一个,判断它是否是高度平衡
数据结构与算法 5703 科普:一篇论文是1946年发表,然而一个没有bug分查找法却是在1962年才出现,间用了16年时间。定义在计算机科学分查找(英语:binarysearch),也称折半
数据结构与算法 6856 题目:判断下方两棵右方是否为左方例1:||/-----------10(10)------\/-------10(10)------\||||/-------5(5
official 498 leetcode589题题目描述给定一个N,返回其节点值前序遍历。例如,给定一个3:返回其前序遍历:[1,3,5,6,2,4]。解题思路递归遍历,深度优先代码(java
数据结构与算法 4603 整理遍历-(递归法)和(非递归法)-笔记先序遍历、序遍历、后续遍历、层级遍历。1.节点信息:packagetree;publicclassNodeE{ privateEe;//数据域
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。