算法系列——二叉搜索树的第k个结点

题目描述

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

解题思路

1，二叉搜索树的中序遍历是排序的，所以先进行中序遍历得到一个有序list 2，在该list里查找到第k个

程序实现

public class Solution { private ArrayList<TreeNode> res=new ArrayList<TreeNode>(); TreeNode KthNode(TreeNode pRoot, int k) { if(pRoot==null||k<=0) return null; inOrder(pRoot,k); if(k>res.size()) return null; return res.get(k-1); } void inOrder(TreeNode node,int k){ if(node==null) return; inOrder(node.left,k); res.add(node); inOrder(node.right,k); } }