剑指offer54 二叉查找树的第 K 个结点

106 阅读 0 评论 70 点赞

我是靠谱客的博主紧张飞机，最近开发中收集的这篇文章主要介绍剑指offer54 二叉查找树的第 K 个结点，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述：
给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。

题目链接：
剑指offer54

思路：二叉查找树的中序遍历是有序的，中序遍历即可找出答案

public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        Stack<TreeNode> stack = new Stack<>();
        while(pRoot != null || !stack.isEmpty()){
            while(pRoot != null){
                stack.push(pRoot);
                pRoot = pRoot.left;
            }
            TreeNode tem = stack.pop();
            k--;
            if(k == 0){
                return tem;
            }
            pRoot = tem.right;
        }
        return null;
    }
}