题解 | #二叉搜索树的第k个结点#
二叉搜索树的第k个结点
http://www.nowcoder.com/practice/ef068f602dde4d28aab2b210e859150a
代码思路：因为二叉搜索树的中序遍历是升序的，因此采用中序遍历，遍历结果用ist保存
根据第k小，可取list.get(k-1);
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
{
TreeNode KthNode(TreeNode pRoot, int k)
{
if(pRoot == null || k == 0)
return null;
return Inorder(pRoot,k);
}
public TreeNode Inorder(TreeNode root, int k)
{
List<TreeNode> list = new ArrayList<TreeNode>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = null;
while(root!=null || !stack.isEmpty())
{
while(root != null)
{
stack.push(root);
root = root.left;
}
if(!stack.isEmpty())
{
root = stack.pop();
list.add(root);
root = root.right;
}
}
return k <= list.size() ? list.get(k-1) : null;
}
}
投递美团等公司10个岗位