文章目录
题目描述
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
示例 2:
输入：inorder = [-1], postorder = [-1]
输出：[-1]
提示:
1
做题记录
- 今日四刷
- 根据中序 + 后序 –> 二叉树
- 还有一个类似的 前序+中序 –> 二叉树
- 这里我们需要记住一个结论，对于做题右帮助
- 如果 前序+中序： 我们需要求出左子树的长度 中序+后序： 我们需要求出右子树的长度 其实很好理解： 因为前序数组的根节点在第一位 后序数组的根节点在最后一位 还需要注意一点：递归的推出条件 对于前序数组来说：
if(i>j)return null;
对于后序数组来说
if(p>q)return null;
代码实现
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return createTree(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
}
public TreeNode createTree(int[] inorder,int i,int j,int[] postorder,int p,int q){
if(p>q){
return null;
}
int k=j;
while(inorder[k]!=postorder[q]){
k--;
}
TreeNode root=new TreeNode(postorder[q]);
int rightLen=j-k;
TreeNode right=createTree(inorder,k+1,j,postorder,q-rightLen,q-1);
TreeNode left=createTree(inorder,i,k-1,postorder,p,q-rightLen-1);
root.left=left;
root.right=right;
return root;
}
}
题目链接
Original: https://blog.csdn.net/C_x_330/article/details/128418409
Author: C_x_330
Title: 106. 从中序与后序遍历序列构造二叉树
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/786316/
转载文章受原作者版权保护。转载请注明原作者出处！