关于java:二叉树题型框架2

把题目的要求细化，搞清楚根节点应该做什么，而后剩下的事件抛给前/中/后序的遍历框架，千万不要跳到递归的细节里，置信你的定义

结构最大二叉树

对于结构二叉树的问题,根节点要做的就是想方法把本人结构进去
咱们必定要遍历数组找到最大值maxVal,把根节点root做进去，而后对maxVal右边的数组和左边的数组进行递归调用，作为root的左右子树。
伪代码

TreeNode constructMaxImumBinaryTree(int[] nums){
if(num is empty){
return null;
}

int maxVal=Integer.MIN_VALUE;
int index=0;

for(int i=0;i<nums.length;i++){
if(nums[i]>maxVal){
maxVal=nums[i];
index=i;
     }
}

TreeNode root=new TreeNode(maxVal);
//递归调用结构左右子树
root.left=constructMaximumBinaryTree(nums[0]...index-1);
root.right=constructMaximumBinaryTree(nums[index+1...nums.length-1]);

return root;
}

对于每个根节点来说，最重要的是找到以后数组中的最大值以及它的索引,而后前序递归调用结构子树

//主函数
TreeNode constructMaximumBinaryTree(int[] nums){
return build(nums,0,nums.length-1);
}

TreeNode build(int[] nums,int lo,int hi){
//base case
if(lo>hi){
return null;
}

//找到数组中最大值和对应的索引
int index=-1,maxVal=Integer.MIN_VALUE;
for(int i=lo;i<=hi;i++){
if(maxVal<nums[i]){
maxVal=nums[i];
index=i;
}
}

TreeNode root=new TreeNode(maxVal);
//递归调用结构左右子树
root.left=build(nums,lo,index-1);
root.right=build(nums,index+1,hi);

return root;
}