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

weblog 460 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 517 和一个head为一个节点链表。如果在,存在一条一直向下路径,且每个点数值恰好一一对应以head为首链表每个节点值,那么请你返回True,否则返回False。一直向下路径意思
weblog 3611 什么是前驱节点和后继节点?某节点前驱节点val值于该节点val值并且值是最大那个节点。某节点后继节点val值大于该节点val值并且值是最那个节点。下面给出一个节点类
official 478 径。说明:叶子节点是指没有子节点节点。示例:输入:1/\23\5输出:["1-2-5","1-3"]解释:所有根节点到叶子节点路径为:1-2-5,1-3解题思路递归得方式遍历(深度优先),
official 442 leetcode110题(简单)原链接https://leetcode-cn.com/problems/balanced-binary-tree/题目描述给定一个,判断它是否是高度平衡
数据结构与算法 5502 科普:一篇论文是1946年发表,然而一个没有bug分查找法却是在1962年才出现,间用了16年时间。定义在计算机科学分查找(英语:binarysearch),也称折半
数据结构与算法 6671 题目:判断下方两棵右方是否为左方例1:||/-----------10(10)------\/-------10(10)------\||||/-------5(5
official 375 leetcode589题题目描述给定一个N,返回其节点值前序遍历。例如,给定一个3:返回其前序遍历:[1,3,5,6,2,4]。解题思路递归遍历,深度优先代码(java
数据结构与算法 4442 整理遍历-(递归法)和(非递归法)-笔记先序遍历、序遍历、后续遍历、层级遍历。1.节点信息:packagetree;publicclassNodeE{ privateEe;//数据域
目录
祝愿神州十三飞行乘组平安归来