题解 | #二叉搜索树的第k个节点#
二叉搜索树的第k个节点
http://www.nowcoder.com/practice/57aa0bab91884a10b5136ca2c087f8ff
解题思路
①二叉搜索树排序
②按照数组索引，直接返回第k小数值
③注意特殊情况（空树、k大于树数量...）的处理
/*
* function TreeNode(x) {
* this.val = x;
* this.left = null;
* this.right = null;
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param proot TreeNode类
* @param k int整型
* @return int整型
*/
function KthNode( proot , k ) {
// write code here
// 先处理特殊情况,空树或k为0，返回-1
if(!proot||k==0)
return -1;
// 初始化有序数组arr
var arr=[];
// 定义递归排序
function OrderArray(root){
if(!root)
return -1;
// 先左
OrderArray(root.left)
arr.push(root.val)
// 后右
OrderArray(root.right)
}
// 调用排序函数，将二叉搜索树插入到有序数组中
OrderArray(proot)
// 如果k大于树长度，返回 -1
if(k>arr.length)
return -1;
return arr[k-1]
}
module.exports = {
KthNode : KthNode
};
查看30道真题和解析
投递完美世界等公司7个岗位