Share 1ms java in-order traverse with result object


  • 0
    S

    If I can modify TreeNode property to hold left size, then it could be O(logN)...

    public class Solution {
    private class Result { 
        int count =0; 
        TreeNode kthNode = null;
    }
    
    public int kthSmallest(TreeNode root, int k) {
        Result result = new Result(); 
        kthSmallestInOrderTraverse(root, k, result);
        return result.kthNode.val; 
    }
    
    private void kthSmallestInOrderTraverse(TreeNode root, int k, Result result) {
        if(root == null) return;
        
        // left nodes
        kthSmallestInOrderTraverse(root.left, k, result); 
        // current node 
        if(result.kthNode == null) { 
            result.count += 1; 
            if(result.count == k) {
                result.kthNode = root; 
            }
        }
        // right nodes 
        if(result.kthNode == null) {
            kthSmallestInOrderTraverse(root.right, k, result);     
        }
    }
    

    }


Log in to reply
 

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