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

    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;
    }