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:
n^2建树
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* build(int l, int r, vector<int> & nums) { int Max = INT_MIN; int tmp = -1; if (l > r) return NULL; for (int i = l; i <= r; ++i) { if (nums[i] > Max) { Max = nums[i]; tmp = i; } } TreeNode * root = new TreeNode(Max); root->left = build(l, tmp - 1, nums); root->right = build(tmp + 1, r, nums); return root; } TreeNode* constructMaximumBinaryTree(vector<int>& nums) { if (nums.size() == 0) return NULL; return build(0, nums.size()-1, nums); } };
leetcode 654. Maximum Binary Tree
原文：http://www.cnblogs.com/pk28/p/7297912.html