Java O(n) time, O(n) space recursive solution


  • 0
    P
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public int kthSmallest(TreeNode root, int k) {
            int[] result = helper(root, k, 1);
            return result[1];
        }
        
        private int[] helper(TreeNode root, int k, int counter) {
            int[] result = new int[2];
            result[0] = counter;
            result[1] = root.val;
            if (root.left == null && root.right == null) {
                return result;
            }
            
            if (root.left != null) {
                result = helper(root.left, k, counter);
                if (result[0] != k) {
                    result[0] = result[0]+1;
                    result[1] = root.val;
                }
            }
            
            if (result[0] == k) {
                return result;
            }
            
            if (root.right != null) {
                result = helper(root.right, k, result[0]+1);
            }
            
            return result;
        }
    }
    

Log in to reply
 

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