本文共 1375 字，大约阅读时间需要 4 分钟。
题目描述：给定一颗二叉树，找出第K大的节点，这个第K大的节点是从小到大的第K个节点，所以也可以说是第K小的节点。对于一颗二叉树来说，其中序遍历就是节点值从小到大的排列，那么我们用一个ArrayList把中序遍历的结果保存下来，找到第K-1个节点就是第K大的节点。因此很容易想到以下的代码：
/*public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/import java.util.ArrayList;public class Solution { TreeNode KthNode(TreeNode pRoot, int k) { //中序遍历的第k-1个节点就是第k大的节点 if(pRoot == null || k<=0) return null; ArrayList aList = new ArrayList(); inOrderRecursive(pRoot,aList); int len = aList.size(); if(len al){ if(root == null){ return; } inOrderRecursive(root.left,al); al.add(root); inOrderRecursive(root.right,al); }} 当然，也可以边遍历，边返回节点，这样可以提高效率，比如当这颗二叉树很大，但是K很小的时候，就会大大的节约时间。代码实现如下： //思路：二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。// 所以，按照中序遍历顺序找到第k个结点就是结果。public class Solution { int index = 0; //计数器 TreeNode KthNode(TreeNode root, int k) { if(root != null){ //中序遍历寻找第k个 TreeNode node = KthNode(root.left,k); if(node != null) return node; index ++; if(index == k) return root; node = KthNode(root.right,k); if(node != null) return node; } return null; }} 转载地址：http://psnqi.baihongyu.com/