榆林建设银行的网站,成都网站设计排名的公司价格,做证明图片的网站,商标注册号题目来源
力扣106从中序和后序遍历序列构造二叉树
题目概述
给定两个整数数组 inorder 和 postorder #xff0c;其中 inorder 是二叉树的中序遍历#xff0c; postorder 是同一棵树的后序遍历#xff0c;请你构造并返回这颗 二叉树 。
思路分析
后序遍历序列的最末尾数…题目来源
力扣106从中序和后序遍历序列构造二叉树
题目概述
给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。
思路分析
后序遍历序列的最末尾数据为树的根节点。 在中序遍历序列中找到树的根节点就可以找到这棵树的左子树范围和右子树范围。 分析方法与从前序与中序遍历序列构造二叉树类似。
代码实现
java实现
public class Solution {MapInteger, Integer inorderIndexMap new HashMap();public TreeNode buildTree(int[] inorder, int[] postorder) {// 中序遍历序列数据与下标映射便于后续查找for (int i 0; i inorder.length; i) {inorderIndexMap.put(inorder[i],i);}return create(inorder, postorder ,0, inorder.length - 1, 0, postorder.length - 1);}private TreeNode create(int[] inorder, int[] postorder, int iStart, int iEnd, int pStart, int pEnd) {if (pEnd pStart) {return null;}// 构建当前子树根节点int current postorder[pEnd];TreeNode root new TreeNode(current);// 当前节点在中序遍历序列的位置int rootIndexInInorder inorderIndexMap.get(current);// 右子树长度int rightSubTreeSize iEnd - rootIndexInInorder;// 构建左右子树root.right create(inorder,postorder, rootIndexInInorder 1, iEnd ,pEnd - rightSubTreeSize, pEnd - 1);root.left create(inorder,postorder, iStart,rootIndexInInorder - 1,pStart, pEnd - rightSubTreeSize - 1);return root;}
}c实现
class Solution {
public:unordered_mapint, int inorder_data_and_index;TreeNode* buildTree(vectorint inorder, vectorint postorder) {// 中序遍历序列数据与下标映射便于后续查找for (int i 0; i inorder.size(); i) {inorder_data_and_index[inorder[i]] i;}return create(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);}TreeNode* create(vectorint inorder, vectorint postorder, int iStart, int iEnd, int pStart, int pEnd) {if (pEnd pStart) {return nullptr;}// 构建当前子树根节点int current postorder[pEnd];TreeNode* root new TreeNode(current);// 当前节点在中序遍历序列的位置int rootIndexInInorder inorder_data_and_index[current];// 右子树长度int rightSubTreeSize iEnd - rootIndexInInorder;// 构建左右子树root-right create(inorder, postorder, rootIndexInInorder 1, iEnd, pEnd - rightSubTreeSize, pEnd - 1);root-left create(inorder, postorder, iStart, rootIndexInInorder - 1, pStart, pEnd - rightSubTreeSize - 1);return root;}
}
