[LeetCode] 654. Maximum Binary Tree
发布时间:2020-12-14 03:18:40 所属栏目:大数据 来源:网络整理
导读: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 by the max
Input: [3,2,1,6,5] Output: return the tree root node representing the following tree: 6 / 3 5 / 2 0 1
最大树: 看到题就想到了递归
代码如下 TreeNode* constructMaximumBinaryTree(vector<int>& nums) { if (nums.empty()) { return NULL; } vector<int>::iterator max_iter = max_element(nums.begin(),nums.end()); TreeNode* root = new TreeNode(*max_iter); vector<int> left_vec(nums.begin(),max_iter); vector<int> right_vec(max_iter + 1,nums.end()); root->left = constructMaximumBinaryTree(left_vec); root->right = constructMaximumBinaryTree(right_vec); return root; } 再看看leetcode上其他人的代码 只需遍历一次
先把 如果 如果 TreeNode* constructMaximumBinaryTree(vector<int>& nums) { auto it = nums.begin(); TreeNode* node = new TreeNode(*it); TreeNode* tmp = NULL; TreeNode* t = NULL; for( ++it; it != nums.end(); ++it){ if (*it > node->val){ tmp = node; node = new TreeNode(*it); node->left = tmp; } else{ tmp = new TreeNode(*it); t = node; while(t->right && t->right->val > tmp->val) t = t->right; tmp->left = t->right; t->right = tmp; } } return node; } 3 2 1 6 0 5 3 2在3的右边,所以在右子树,1也是同理 3 2 1 6比3大,3,2,1都在6的左边 6 / 3 2 1 0在6的右边且比0小 6 / 3 0 2 1 插入5的比较关键,先从根节点6开始向右边找到最后一个比5小的数,也就是0,把0变成5的左节点,再将5变成6的右节点 6 / 3 5 / 2 0 1 多举个例子表明是要找的是最后一个比要插入的值大的节点 8 6 4 5 8 6 4 接下来插入5,根节点8的右子树中最后一个比5大的节点是6,所以5要为6的右节点(最大树中越高的节点越大) 8 6 5 / 4 8 6 5 / 4 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |