关于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;
}