Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Recursive solution: avoid copy array
- //Time: O(n), 7ms
- //Space: O(h)
- class Solution {
- public TreeNode constructMaximumBinaryTree(int[] nums) {
- return constructR(nums, 0, nums.length);
- }
- private TreeNode constructR(int[] nums, int begin, int end) {
- if(begin >= end) return null;
- int max = begin;
- for(int i = begin; i < end; i++) {
- if(nums[i] > nums[max]) {
- max = i;
- }
- }
- TreeNode root = new TreeNode(nums[max]);
- root.left = constructR(nums, begin, max);
- root.right = constructR(nums, max + 1, end);
- return root;
- }
- }
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
Add Comment
Please, Sign In to add comment