面試題63. 二叉搜尋樹的第k個結點

題目描述

給定一顆二叉搜尋樹，請找出其中的第k大的結點。例如，

\ 
  3 7 
 /\ /\
2 4 6 8      

按結點數值大小順序第三個結點的值為4。

思路：

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/

import java.util.LinkedList;

public class Solution

    public LinkedList<TreeNode> list = new LinkedList<TreeNode>();

    //中序周遊 遞歸
    TreeNode KthNode(TreeNode pRoot, int k) {
        if(pRoot == null || k <= 0) return null;
        inOrder(pRoot);
        if(k > list.size()) return null;
        return list.get(k-1);
    }

    public void inOrder(TreeNode root) {
        if(root == null) return ;
        if(root.left == null && root.right == null) {
            list.add(root);
            return