题解 | #二叉搜索树的第k个结点#Morris遍历实现的O(1)空间复杂度

二叉搜索树的第k个结点

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

    TreeNode KthNode(TreeNode pRoot, int k) {
        //Morris遍历
        TreeNode tmp = pRoot;
        TreeNode res = null;
        int cnt = 0;
        while(tmp!=null){
            if(tmp.left!=null){
                //去到左边的最右节点
                TreeNode mostRight = tmp.left;
                while(mostRight.right!=null&&mostRight.right!=tmp){
                    mostRight = mostRight.right;
                }
                //第一次到就向左走
                if(mostRight.right==null){
                    mostRight.right = tmp;
                    tmp = tmp.left;
                    continue;
                }
                //第二次到
                if(++cnt==k){
                    res = tmp;
                }
                mostRight.right = null;
            }else{
                //第一次到
                //到最左节点肯定cnt为0
                if(++cnt==k){
                    res = tmp;
                }
            }
            tmp = tmp.right;
        }
        return res;
    }
waigo的刷题之路 文章被收录于专栏

收录平时刷题的题解

全部评论

相关推荐

06-15 20:57
已编辑
门头沟学院 Java
CARLJOSEPH...:年轻人有傲气很正常,但是建议工作前洗净傲气。 说实在的,什么奖学金什么奖项的都很一般。尊重你的老师,在有时间的时候去上课,真遇到走不开的事,请态度端正地向你的老师说明情况,请求请假。我相信任何一个有师德的老师都会允许的(我的老师就是这样)。
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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