刷题计划day17 二叉树（七）【 从中序与后序遍历序列构造二叉树】【从中序与后序遍历序列构造二叉树】【最大二叉树】
⚡刷题计划day17 二叉树（七）继续，二叉树会有十期专题，可以点个免费的赞哦~
目录
题目一:106. 从中序与后序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
此题题解参考leetcode即可，推荐:106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）题解
class Solution {
HashMap<Integer,Integer> inorderArrayMap = new HashMap<>();
int[] post;
public TreeNode buildTree(int[] inorder, int[] postorder) {
for(int i=0;i<inorder.length;i++){
inorderArrayMap.put(inorder[i],i);//将节点值及索引全部记录在哈希表中
}
post = postorder;
TreeNode root = buildTree(0,inorder.length-1,0,post.length-1);
return root;
}
public TreeNode buildTree(int inorderStart,int inorderEnd,int postorderStart,int postorderEnd){
if(inorderStart>inorderEnd || postorderStart>postorderEnd){
return null;
}
int root = post[postorderEnd];//根据后序遍历结果，取得根节点
int rootIndexInInorderArray = inorderArrayMap.get(root);//获取对应的索引
TreeNode node = new TreeNode(root);//创建该节点
node.left = buildTree(inorderStart,rootIndexInInorderArray-1,postorderStart,postorderStart+rootIndexInInorderArray-inorderStart-1);
node.right = buildTree(rootIndexInInorderArray+1,inorderEnd,postorderStart+rootIndexInInorderArray-inorderStart,postorderEnd-1);
return node;
}
}题目二：106. 从中序与后序遍历序列构造二叉树
-
从中序与后序遍历序列构造二叉树
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
class Solution {
HashMap<Integer,Integer> inorderArrrayMap = new HashMap<>();
int[] pre;
public TreeNode buildTree(int[] preorder, int[] inorder) {
for(int i=0;i<inorder.length;i++){
inorderArrrayMap.put(inorder[i],i);
}
pre = preorder;
TreeNode root = buildTree(0,inorder.length-1,0,preorder.length-1);
return root;
}
public TreeNode buildTree(int inorderStart,int inorderEnd,int preorderStart,int preorderEnd){
if(inorderEnd<inorderStart || preorderEnd<preorderStart){
return null;
}
int root = pre[preorderStart];
int rootArrayIndex = inorderArrrayMap.get(root);
TreeNode node = new TreeNode(root);
int leftLength = rootArrayIndex-inorderStart;
node.left = buildTree(inorderStart,rootArrayIndex-1,preorderStart+1,preorderStart+leftLength);
node.right = buildTree(rootArrayIndex+1,inorderEnd,preorderStart+leftLength+1,preorderEnd);
return node;
}
}题目三：654. 最大二叉树
-
最大二叉树
(https://leetcode.cn/problems/maximum-binary-tree/description/)
根据题目，我们很容易会想到通过递归的方式对本题进行解答。因为无论是拆分出来左子数组还是右子数组，那么对于子数组的操作，依然都是一样的逻辑。所以，初步思路上面，我们首先确定以递归的方式进行解题。
递归三部曲：
1.确定递归函数的参数和返回值
参数需要穿入数组，然后我们需要以当前数组的最大值进行分割，所以还需要下标索引，然后需要返回根节点。
然后还需要一个通用的方法进行查找当前数组的最大值下标，我们可以抽象出来。
TreeNode build(int[] nums,int startIndex,int endIndex)int maxIndex(int[] nums,int startIndex,int endIndex)2.确定终止条件
当开始下标>结束下标，说明此部分数组为空，返回null值即可。
3.确定单层递归的逻辑
找到数组最大值对应下标，然后最大值构造根节点，使用下标进一步分割数组，
具体代码如下：
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return build(nums,0,nums.length-1);
}
public TreeNode build(int[] nums,int startIndex,int endIndex){
if(startIndex>endIndex){
return null;
}
int maxIndex = maxIndex(nums,startIndex,endIndex);
TreeNode newNode = new TreeNode(nums[maxIndex]);
newNode.left = build(nums,startIndex,maxIndex-1);
newNode.right = build(nums,maxIndex+1,endIndex);
return newNode;
}
public int maxIndex(int[] nums,int startIndex,int endIndex){
int maxIndex = startIndex;
for(int i=startIndex+1;i<=endIndex;i++){
maxIndex = nums[maxIndex] < nums[i] ? i : maxIndex;
}
return maxIndex;
}
}点个免费的赞吧🌹
原文地址：https://blog.csdn.net/weixin_72499901/article/details/143696202
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！