654. Maximum Binary Tree
发布时间:2020-12-14 03:19:27 所属栏目:大数据 来源:网络整理
导读:题目描述: Given an integer array with no duplicates. A maximum tree building on this array is defined as follow: The root is the maximum number in the array. The left subtree is the maximum tree constructed from left part subarray divided
题目描述: 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,5] Output: return the tree root node representing the following tree: 6 / 3 5 / 2 0 1 ? Note:
解题思路: 树的定义是递归的,一般构造方法也使用递归方法。 代码: 1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x),left(NULL),right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 TreeNode* constructMaximumBinaryTree(vector<int>& nums) { 13 if (nums.size() == 0) return NULL; 14 if (nums.size() == 1) { 15 TreeNode* node = new TreeNode(nums[0]); 16 return node; 17 } 18 int index = findMax(nums); 19 TreeNode* node = new TreeNode(nums[index]); 20 vector<int> left; 21 vector<int> right; 22 for(int i = 0; i < index; ++i) { 23 left.push_back(nums[i]); 24 } 25 for(int i = index + 1; i < nums.size(); ++i) { 26 right.push_back(nums[i]); 27 } 28 node->left = constructMaximumBinaryTree(left); 29 node->right = constructMaximumBinaryTree(right); 30 return node; 31 } 32 int findMax(const vector<int>& nums) { 33 if (nums.size() == 0) 34 return -1; 35 int index = 0; 36 int max = nums[0]; 37 for (int i = 0; i < nums.size(); ++i) { 38 if (nums[i] > max) { 39 max = nums[i]; 40 index = i; 41 } 42 } 43 return index; 44 } 45 }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |