0%

最大二叉树

发表于 分类于 ， Disqus：

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

二叉树的根是数组中的最大元素。

  • 左子树是通过数组中最大值左边部分构造出的最大二叉树。
  • 右子树是通过数组中最大值右边部分构造出的最大二叉树。
  • 通过给定的数组构建最大二叉树，并且输出这个树的根节点。
1
2
3
4
5
6
7
8
9
10
输入: [3,2,1,6,0,5]
输入: 返回下面这棵树的根节点：

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

递归实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
		if (nums.empty()) {
			return NULL;
		}
		auto iter = max_element(nums.begin(), nums.end());
		vector<int> left, right;
		for (auto i = nums.begin(); i != nums.end(); i++) {
			if (i < iter) {
				left.push_back(*i);
			}
			if (i > iter) {
				right.push_back(*i);
			}
		}
		TreeNode* root = new TreeNode(*iter);
		root->left = constructMaximumBinaryTree(left);
		root->right = constructMaximumBinaryTree(right);
		return root;
	}