二叉搜索树的第k个节点

二叉搜索树的第k个结点

http://www.nowcoder.com/questionTerminal/ef068f602dde4d28aab2b210e859150a

一是利用大家都能想到的中序遍历递归法:

public class Solution {
    List<TreeNode> list = new ArrayList<>();
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot == null || k < 1){
            return null;
        }
        minOrder(pRoot, k);
        //当k超过节点个数时
        if(list.size() < k)
            return null;
        return list.get(k-1);
    }

    void minOrder(TreeNode pRoot, int k){
        if(pRoot != null){
            minOrder(pRoot.left, k);
            list.add(pRoot);
            k = k - 1;
            if(k == 0)
                return;
            minOrder(pRoot.right, k);
        }
    }
}

二是利用栈来弹出第k个节点:
public class Solution {
    List<TreeNode> list = new ArrayList<>();
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot == null || k < 1){
            return null;
        }
        TreeNode node = pRoot;
        int count = 0;
        Stack<TreeNode> stack = new Stack<>();

        while(!stack.isEmpty() || node != null){
            //中序遍历
            //遍历到左子树为空
            if(node != null){
                stack.push(node);
                node = node.left;
            }else{
                //再弹出去
                node = stack.pop();
                count++;
                //当弹到第k个时,直接返回
                if(count == k)
                    return node;
                //否则,遍历右子树
                node = node.right;
            }
        }
        return null;
    }

}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-04 18:02
好不容易拿到了字节Offer,鼠鼠做后端的,但家里人觉得可能被裁员不稳定,让鼠鼠去投国企,现在好纠结到底该咋选
文档传偷助手:该投就投吧,不过建议别放弃offer 拿到手里的才是最好的
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
陈逸轩1205:才105 哥们在养生呢
点赞 评论 收藏
分享
机械打工仔:我来告诉你原因,是因为sobb有在线简历,有些HR为了快会直接先看在线简历,初步感觉不合适就不会找你要详细的了
投了多少份简历才上岸
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 14:23
steelhead:你回的有问题,让人感觉你就是来学习的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务