The trick here is to name the state correctly, then let the implementation follow. For 654. Maximum Binary Tree, the solution in this repository is mainly a two pointers solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are constructMaximumBinaryTree, findMaxIndex, constructMaxSubtree.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:
03
04The root is the maximum number in the array.
05The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
06The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.
07Construct the maximum tree by the given array and output the root node of this tree.
08
09Example 1:
10Input: [3,2,1,6,0,5]
11Output: return the tree root node representing the following tree:
12
13 6
14 / \
15 3 5
16 \ /
17 2 0
18 \
19 1
20Note:
21The size of the given array will be in the range [1,1000].
22**/
23
24/**
25 * Definition for a binary tree node.
26 * struct TreeNode {
27 * int val;
28 * TreeNode *left;
29 * TreeNode *right;
30 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
31 * };
32 */
33
34//Your runtime beats 8.47 % of cpp submissions.
35// class Solution {
36// public:
37// TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
38// //std::max_element : Returns iterator to the greatest element. From C++11
39// //need to use *max(std::begin(nums), std::end(nums)) to access the greatest element.
40// //max_element(std::begin(nums), std::end(nums)) - std::begin(nums) to get the index of greatest element
41// int maxIndex = max_element(std::begin(nums), std::end(nums)) - std::begin(nums);
42// int max = *max_element(std::begin(nums), std::end(nums));
43// // cout << maxIndex << endl;
44
45// TreeNode* root= new TreeNode(max); //new an object an assign its address to a pointer to the object
46// if(nums.begin() < nums.begin()+maxIndex){
47// vector<int> leftnum = vector<int>(nums.begin(), nums.begin()+maxIndex);
48// root->left = constructMaximumBinaryTree(vector<int>(nums.begin(), nums.begin()+maxIndex));
49// }else{
50// root->left = NULL;
51// }
52
53// if(nums.begin()+maxIndex+1 < nums.end()){
54// vector<int> rightnum = vector<int>(nums.begin()+maxIndex+1, nums.end());
55// root->right = constructMaximumBinaryTree(rightnum);
56// }else{
57// root->right = NULL;
58// }
59
60// return root;
61// }
62// };
63
64/**
65Approach #1 Recursive Solution[Accepted]
66The current solution is very simple. We make use of a function construct(nums, l, r), which returns the maximum binary tree consisting of numbers within the indices ll and rr in the given numsnums array(excluding the r^{th}r
67th element).
68
69The algorithm consists of the following steps:
70
71Start with the function call construct(nums, 0, n). Here, nn refers to the number of elements in the given numsnums array.
72
73Find the index, max_i, of the largest element in the current range of indices (l:r-1)(l:r−1). Make this largest element, $nums[max_i] as the local root node.
74
75Determine the left child using construct(nums, l, max_i). Doing this recursively finds the largest element in the subarray left to the current largest element.
76
77Similarly, determine the right child using construct(nums, max_i + 1, r).
78
79Return the root node to the calling function.
80
81Complexity Analysis
82
83Time complexity : O(n^2).
84The function construct is called nn times. At each level of the recursive tree, we traverse over all the nn elements to find the maximum element. In the average case, there will be a log(n) levels leading to a complexity of O(nlog(n)). In the worst case, the depth of the recursive tree can grow upto n, which happens in the case of a sorted numsnums array, giving a complexity of O(n^2).
85
86Space complexity : O(n). The size of the setset can grow upto nn in the worst case. In the average case, the size will be log(n) for nn elements in numsnums, giving an average case complexity of O(log(n))
87**/
88
89//solution by karanrgoswami
90//Your runtime beats 71.37 % of cpp submissions.
91/*
92Lets break this problem down:
931.) Find maximum element's index as maxindex
942.) create vector[maxindex] as root return the root.
953.) then run the same function over left subtree and assign the returned output to the left of the first root created (recursion)
964.) then run the same function over rught subtree and assign the returned node to the right of the first root created (recursion)
97
98*/
99class Solution {
100
101private:
102 int findMaxIndex(vector<int> &nums, int l, int r)
103 {
104 int maxI = l;
105
106 for (int i = l; i<=r ; i++)
107 {
108 if(nums[i] >= nums[maxI])
109 maxI = i;
110 }
111 return maxI;
112 }
113
114 TreeNode* constructMaxSubtree(vector<int>& nums, int l, int r)//l, r are inclusive
115 {
116 if(l>r) return NULL;//not empty when l==r
117 int maxI = findMaxIndex(nums, l, r); // this is max index so this nums will be root
118 TreeNode* root = new TreeNode(nums[maxI]);
119 //Root is constructed now make children
120 root->left = constructMaxSubtree(nums,l,maxI-1);
121 root->right = constructMaxSubtree(nums, maxI+1,r);
122 return root;
123 }
124
125public:
126 TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
127 if(nums.size() == 0) return NULL;
128 if(nums.size() == 1) return new TreeNode(nums[0]);
129 TreeNode *maxTreeRoot;
130 maxTreeRoot = constructMaxSubtree(nums,0,(nums.size()-1));
131 return maxTreeRoot;
132 }
133};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.