Java Recursion Solution with In-order Traversal


  • 1
    J

    Actually, this array nums is the in-order expression of the BST. So the center element is its root, the left is its left sub-tree and the right is its right sub-tree.

        public TreeNode sortedArrayToBST(int[] nums) {
            if (nums == null || nums.length == 0)
                return null;
            return recursionNode(nums, 0, nums.length - 1);
        }
    
        private TreeNode recursionNode(int[] nums, int start, int end){
            if (start > end) return null;
            if (start == end) return new TreeNode(nums[start]);
            int center = (end + 1 - start) / 2 + start;
            TreeNode root = new TreeNode(nums[center]);
            root.left = recursionNode(nums, start, center - 1);
            root.right = recursionNode(nums, center + 1, end);
            return root;
        }
    

  • 0
    L

    I thinks this is preorder traversal.


  • 0
    J

    It is in-order because in-order is left -> root -> right and in BST left < root < right. So you can get a sorted array. But in pre-order, the order will be root -> left -> right, root > left, you can't get a sorted array.


  • 0
    S

    @liang54 The solution is not in-order traverse, but we judge the sorted array as the result of in-order traverse of a BST. And recursively pick the middle number as root.


  • 0
    J

    Yes, so I only said this array nums is the in-order expression of the BST. just want to inspire someone.


  • 0
    L

    @JackQin I see your point. Thanks for the explanation. :)


Log in to reply
 

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