O(1) space O(n) time Morris Traversal java


  • 0
    C
    public class Solution {
        public int kthSmallest(TreeNode root, int k) {
            int count = 0;
            int result = 0;
            TreeNode pre, curr;
            curr = root;
            while(curr != null) {
                if(curr.left == null) {
                    count++;
                    if(count == k) {
                        result = curr.val;
                    }
                    curr = curr.right;
                } else {
                    pre = curr.left;
                    
                    while(pre.right != null && pre.right != curr)
                        pre = pre.right;
                        
                    if(pre.right == null) {
                        pre.right = curr;
                        curr = curr.left;
                    } else {
                        pre.right = null;
                        count++;
                        if(count == k) {
                            result = curr.val;
                        }
                        curr = curr.right;
                    }
                }
            }
            return result;
        }
    }
    

Log in to reply
 

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