Table of Contents
Problem
You are given an integer array nums
with no duplicates. A maximum binary tree can be built recursively from nums
using the following algorithm:
- Create a root node whose value is the maximum value in
nums
. - Recursively build the left subtree on the subarray prefix to the left of the maximum value.
- Recursively build the right subtree on the subarray suffix to the right of the maximum value.
Return the maximum binary tree built from nums
.
Example 1:
Input: nums = [3,2,1,6,0,5] Output: [6,3,5,null,2,0,null,null,1] Explanation: The recursive calls are as follow: - The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5]. - The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1]. - Empty array, so no child. - The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1]. - Empty array, so no child. - Only one element, so child is a node with value 1. - The largest value in [0,5] is 5. Left prefix is [0] and right suffix is []. - Only one element, so child is a node with value 0. - Empty array, so no child.
Example 2:
Input: nums = [3,2,1] Output: [3,null,2,null,1]
Constraints:
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
- All integers in
nums
are unique
Source: Leetcode 654. Maximum Binary Tree
Solution
We can solve this problem by following the instructions in problem description. We can recursively find the largest element from input array, and then divide the array into two parts. For each part apply the same method of finding max value. In each step we will create a new node with the max value. Finally, when there is no way to split the array, the recursion will return null.
Below is the code for understanding.
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int get_max_index(vector<int>& nums, int left, int right){ int max_index = left; for(int i = left; i <= right; i++){ if(nums[max_index] < nums[i]){ max_index = i; } } return max_index; } TreeNode* rec(vector<int>& nums, int left, int right){ if(left > right) return NULL; int max_index = get_max_index(nums, left, right); TreeNode* node = new TreeNode(nums[max_index]); node->left = rec(nums, left, max_index - 1); node->right = rec(nums, max_index + 1, right); return node; } TreeNode* constructMaximumBinaryTree(vector<int>& nums) { int len = nums.size(); return rec(nums, 0, len - 1); } };
Conclusion
This is a straight forward recursion problem. If it is not properly understood, please write some comments. Happy coding 🙂
Your article gave me a lot of inspiration, I hope you can explain your point of view in more detail, because I have some doubts, thank you. 20bet
Dear foolishhungry.com owner, Your posts are always well-supported by facts and figures.
Hello foolishhungry.com admin, You always provide useful links and resources.
Hello foolishhungry.com webmaster, You always provide useful links and resources.
Hi foolishhungry.com administrator, Your posts are always well-referenced and credible.
Hi foolishhungry.com owner, Thanks for the in-depth post!
To the foolishhungry.com owner, You always provide valuable information.
To the foolishhungry.com webmaster, Thanks for the well-structured and well-presented post!
Hello foolishhungry.com admin, Keep sharing your knowledge!
Hi foolishhungry.com owner, Your posts are always well-supported by research and data.
Your article helped me a lot, is there any more related content? Thanks! https://www.binance.com/sl/register?ref=PORL8W0Z
Dear foolishhungry.com admin, Your posts are always well-referenced and credible.
To the foolishhungry.com webmaster, You always provide helpful information.
Your article helped me a lot, is there any more related content? Thanks! https://accounts.binance.com/bg/register?ref=UM6SMJM3
Thanks for sharing. I read many of your blog posts, cool, your blog is very good. https://www.binance.info/pt-BR/join?ref=P9L9FQKY
Can you be more specific about the content of your article? After reading it, I still have some doubts. Hope you can help me. https://www.binance.info/zh-TC/join?ref=B4EPR6J0
Your point of view caught my eye and was very interesting. Thanks. I have a question for you. https://www.binance.info/sk/join?ref=WTOZ531Y
Thanks for sharing. I read many of your blog posts, cool, your blog is very good. https://www.binance.info/pl/join?ref=53551167
Your point of view caught my eye and was very interesting. Thanks. I have a question for you. https://www.binance.info/join?ref=JHQQKNKN
Your point of view caught my eye and was very interesting. Thanks. I have a question for you.
Can you be more specific about the content of your article? After reading it, I still have some doubts. Hope you can help me.
https://virtual-local-numbers.com
відеограф на весілля рим
https://cellphoneforums.net/member-433607-budvacarscom.html
I consider, that you commit an error. I suggest it to discuss. Write to me in PM, we will communicate.
https://1x-bet-india.com
Hi foolishhungry.com owner, Your posts are always well written and informative.