剑指Offer——JZ62 二叉树中的第K个结点

题目描述

---

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

题目分析

---

模板题，二叉搜索树，通过中序遍历即可得到一个非递减序列，在遍历的过程中使用一个count变量来标识当前已经过遍历的结点数目，当count等于k时，表示已经找到第k小的结点，即可返回。

代码

---

/* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ import java.util.*; //根据二叉搜索树的性质，中序遍历即可得到一个严格单调递增的序列，进而得到第K小的结点 //中间利用一个count变量表示当前已遍历到结点的数量，当count==k时即表示已找到第k小结点 public class Solution { TreeNode KthNode(TreeNode pRoot, int k) { if(pRoot == null){ return null; } if(k <= 0){ return null; } Stack<TreeNode> stack = new Stack<>(); //记录当前的第count小数 int count = 0; while(pRoot != null || !stack.empty()){ if(pRoot != null){ stack.push(pRoot); pRoot = pRoot.left; }else{ //此时已经找到最左边的结点了，且最左边的结点已入栈 pRoot = stack.pop(); count++; //当count等于k时，即表示已找到第k小的结点 if(count == k){ return pRoot; } pRoot = pRoot.right; } } //若没有找到，说明k不符合要求，即k是大于遍历后形成的序列的元素数量，需要返回null return null; } }