题目描述
给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / / 3 7 // // 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
算法解析： 由于二叉树的特性，如果左子树不为空，所有左子树上的结点都小于等于根节点，如果右子树不为空，所有右子树上的结点都大于等于根节点，那么我们利用中序遍历，即可得到所有结点按值大小顺序排列的结果。
代码如下：
TreeNode KthNode(TreeNode PRoot, int k) { if (pRoot == null){ return null; }else if (k <= 0){ return null; } Stack<TreeNode> stack = new Stack<>(); TreeNode temp = pRoot; int count = 0; while (temp != null || !stack.isEmpty()){ while (temp != null){ stack.push(temp); temp = temp.left; } if (!stack.isEmpty()){ TreeNode data = stack.pop(); count ++; if (count == k){ return data; } temp = data.right; } } return null; }新闻热点
疑难解答
