【力扣每日一题】力扣106从中序和后序遍历序列构造二叉树

题目来源

力扣106从中序和后序遍历序列构造二叉树

题目概述

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

思路分析

后序遍历序列的最末尾数据为树的根节点。 在中序遍历序列中找到树的根节点就可以找到这棵树的左子树范围和右子树范围。 分析方法与从前序与中序遍历序列构造二叉树类似。

代码实现

java实现

public class Solution {Map<Integer, 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_map<int, int> inorder_data_and_index;TreeNode* buildTree(vector<int>& inorder, vector<int>& 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(vector<int>& inorder, vector<int>& 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;}
}