654. Maximum Binary Tree 最大节点劈开,然后左边、右边排序
[抄题]: 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
?[暴力解法]: 时间分析: 空间分析: ?[优化后]: 时间分析: 空间分析: [奇葩输出条件]: [奇葩corner case]: ? TreeNode返回空值对应的是null
? [思维问题]: 不知道dc怎么写:recursion的条件是start end就行了。 [英文数据结构或算法,为什么不用别的数据结构或算法]: [一句话思路]: [输入量]:空:?正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入): [画图]: [一刷]:
[二刷]: [三刷]: [四刷]: [五刷]: ? [五分钟肉眼debug的结果]: [总结]: ? buildtree必须写root.left root.right,recursion的条件是start end就行了。 [复杂度]:Time complexity: O(nlgn) Space complexity: O(n) [算法思想:迭代/递归/分治/贪心]: [关键模板化代码]: [其他解法]: [Follow Up]: [LC给出的题目变变变]: ?[代码风格] : ?[是否头一次写此类driver funcion的代码] : ?[潜台词] : ? /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode constructMaximumBinaryTree(int[] nums) { //corner case if (nums == null || nums.length == 0) return null; //utilize return constructHelper(nums,nums.length - 1); } public TreeNode constructHelper(int[] nums,int start,int end) { //exit requirement if (start > end) return null; //find the max int maxIdx = start; for (int i = start + 1; i <= end; i++) { if (nums[i] > nums[maxIdx]) maxIdx = i; } TreeNode root = new TreeNode(nums[maxIdx]); //recursive in left and right root.left = constructHelper(nums,start,maxIdx - 1); root.right = constructHelper(nums,maxIdx + 1,end); //return return root; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |