Using Morris Traversal


  • 0
    R
    public class Solution {
        public int kthSmallest(TreeNode root, int k) {
            while(root != null){
                if(root.left == null){
                    if(--k == 0)
                        return root.val;
                    root = root.right;
                }
                else{
                    TreeNode run = root.left;
                    while(run.right != null && run.right != root){
                        run = run.right;
                    }
                    if(run.right == null){
                        run.right = root;
                        root = root.left;
                    }
                    else{
                        if(--k == 0)
                            return root.val;
                        run.right = null;
                        root = root.right;
                    }
                }
            }
            return -1;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.