108. Convert Sorted Array to Binary Search Tree

二刷 05/2022

Version #1 Recursion

Runtime: 1 ms, faster than 25.32% of Java online submissions for Convert Sorted Array to Binary Search Tree.

Memory Usage: 43.6 MB, less than 53.88% of Java online submissions for Convert Sorted Array to Binary Search Tree.

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode() {}

 *     TreeNode(int val) { this.val = val; }

 *     TreeNode(int val, TreeNode left, TreeNode right) {

 *         this.val = val;

 *         this.left = left;

 *         this.right = right;

 *     }

 * }

 */

class Solution {

    public TreeNode sortedArrayToBST(int[] nums) {

        return helper(nums, 0, nums.length - 1);

    }

    

    private TreeNode helper(int[] nums, int start, int end) {

        if (start > end) {

            return null;

        }

        int mid = start + (end - start) / 2;

        TreeNode node = new TreeNode(nums[mid]);

        node.left = helper(nums, start, mid - 1);

        node.right = helper(nums, mid + 1, end);

        return node;

    }

}

Version #2 Iteration with Stack

Runtime: 5 ms, faster than 25.32% of Java online submissions for Convert Sorted Array to Binary Search Tree.

Memory Usage: 43.3 MB, less than 65.50% of Java online submissions for Convert Sorted Array to Binary Search Tree.

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode() {}

 *     TreeNode(int val) { this.val = val; }

 *     TreeNode(int val, TreeNode left, TreeNode right) {

 *         this.val = val;

 *         this.left = left;

 *         this.right = right;

 *     }

 * }

 */

class Solution {

    class NodeInfo {

        int start, end;

        TreeNode node;

        public NodeInfo(TreeNode node, int start, int end) {

            this.start = start;

            this.end = end;

            this.node = node;

        }

    }

    public TreeNode sortedArrayToBST(int[] nums) {

        // Use a stack to do a pre order traversal of the tree

        if (nums == null || nums.length == 0) {

            return null;

        }

        int start = 0, end = nums.length - 1;

        TreeNode root = new TreeNode(nums[(start + end) / 2]);

        NodeInfo rootInfo = new NodeInfo(root, start, end);

        Stack<NodeInfo> stack = new Stack<>();

        stack.push(rootInfo);

        while (!stack.isEmpty()) {

            NodeInfo currInfo = stack.pop();

            int mid = (currInfo.start + currInfo.end) / 2;

            // System.out.printf("start%d, end%d,mid%d -> node %d\n", currInfo.start, currInfo.end, mid, currInfo.node.val);

            NodeInfo right = buildNodeInfo(nums, mid + 1, currInfo.end);

            NodeInfo left = buildNodeInfo(nums, currInfo.start, mid - 1);

            

            if (right != null) {

                currInfo.node.right = right.node;

                stack.push(right);

            }

            if (left != null) {

                currInfo.node.left = left.node;

                stack.push(left);

            }

        }

        return root;

    }

    

    private NodeInfo buildNodeInfo(int[] nums, int start, int end) {

        if (start > end) {

            return null;

        }

        return new NodeInfo(new TreeNode(nums[(start + end) / 2]), start, end);

    }

}

一刷

Version #2 Iteration[TODO]
好像很复杂啊。。。

Version #1 Recursion  13.60 %
public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }
    private TreeNode sortedArrayToBST(int[] nums, int start, int end) {
        if (start > end) return null;
        if (start == end) return new TreeNode(nums[start]);
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(nums, start, mid - 1);
        root.right = sortedArrayToBST(nums, mid + 1, end);
        return root;
    }
}