Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:
Construct the maximum tree by the given array and output the root node of this tree.
Example 1:
Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:
6
/ 3 5
\ /
2 0
1
Note:
给一个数组，以数组中的最大值为根结点创建一个最大二叉树，分隔出的左右部分再分别创建最大二叉树。
解法：递归
Java:
public class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
if (nums == null) return null;
return build(nums, 0, nums.length - 1);
}
private TreeNode build(int[] nums, int start, int end) {
if (start > end) return null;
int idxMax = start;
for (int i = start + 1; i <= end; i++) {
if (nums[i] > nums[idxMax]) {
idxMax = i;
}
}
TreeNode root = new TreeNode(nums[idxMax]);
root.left = build(nums, start, idxMax - 1);
root.right = build(nums, idxMax + 1, end);
return root;
}
}
Python:
# Time: O(n)
# Space: O(n)
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def constructMaximumBinaryTree(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
# https://github.com/kamyu104/LintCode/blob/master/C++/max-tree.cpp
nodeStack = []
for num in nums:
node = TreeNode(num);
while nodeStack and num > nodeStack[-1].val:
node.left = nodeStack.pop()
if nodeStack:
nodeStack[-1].right = node
nodeStack.append(node)
return nodeStack[0]
C++:
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
if (nums.empty()) return NULL;
int mx = INT_MIN, mx_idx = 0;
for (int i = 0; i < nums.size(); ++i) {
if (mx < nums[i]) {
mx = nums[i];
mx_idx = i;
}
}
TreeNode *node = new TreeNode(mx);
vector<int> leftArr = vector<int>(nums.begin(), nums.begin() + mx_idx);
vector<int> rightArr = vector<int>(nums.begin() + mx_idx + 1, nums.end());
node->left = constructMaximumBinaryTree(leftArr);
node->right = constructMaximumBinaryTree(rightArr);
return node;
}
};
C++:
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
if (nums.empty()) return NULL;
return helper(nums, 0, nums.size() - 1);
}
TreeNode* helper(vector<int>& nums, int left, int right) {
if (left > right) return NULL;
int mid = left;
for (int i = left + 1; i <= right; ++i) {
if (nums[i] > nums[mid]) {
mid = i;
}
}
TreeNode *node = new TreeNode(nums[mid]);
node->left = helper(nums, left, mid - 1);
node->right = helper(nums, mid + 1, right);
return node;
}
};
C++:
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
vector<TreeNode*> v;
for (int num : nums) {
TreeNode *cur = new TreeNode(num);
while (!v.empty() && v.back()->val < num) {
cur->left = v.back();
v.pop_back();
}
if (!v.empty()) {
v.back()->right = cur;
}
v.push_back(cur);
}
return v.front();
}
};
[LeetCode] 654. Maximum Binary Tree 最大二叉树
原文：https://www.cnblogs.com/lightwindy/p/9854561.html