[数据结构与算法]二叉树搜索第k个节点

题目描述

给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。

输入

{5,3,7,2,4,6,8},3

输出

4

解题思路

将这个二叉搜索树输出到数组，排序，得到结果

代码如下

import java.util.*;

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    
    public TreeNode(int val) {
        this.val = val;
    }
}


public class Solution {
    ArrayList<Integer> prevorder(TreeNode pRoot,ArrayList<Integer> list){
        if(pRoot == null)return list;
        list.add(pRoot.val);
        prevorder(pRoot.left,list);
        prevorder(pRoot.right,list);
        
        return list;
    }
    TreeNode KthNode(TreeNode pRoot, int k) {
        if(pRoot == null)return null;
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Integer> ret = prevorder(pRoot,list);
        int[] arr = new int[ret.size()];
        for(int i = 0;i < list.size();i++){
            arr[i] = ret.get(i);
        }
        Arrays.sort(arr);
        if(k < 1 || k > list.size())return null;
        TreeNode tmp = new TreeNode(arr[k-1]);
        return tmp;
    }
}