做网站的开场白,备案网站内容说明,wordpress 百度地图xml,北京响应式的网站目录链接#xff1a;
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目#xff1a;
https://github.com/September26/java-algorithms 原题链接#xff1a;
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 描述#xff1a;
给定两个… 目录链接
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目
https://github.com/September26/java-algorithms 原题链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台 描述
给定两个整数数组 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 inorder.length 3000postorder.length inorder.length-3000 inorder[i], postorder[i] 3000inorder 和 postorder 都由 不同 的值组成postorder 中每一个值都在 inorder 中inorder 保证是树的中序遍历postorder 保证是树的后序遍历 解题思路
1.和105题差不多只不过后序遍历的最后一个数字一定是根节点。中序遍历中找到这个根节点就可以分成左右两份分别对应左子树和右子树。
2.所以我们使用和105题一样的策略唯一要改的就是传入的区间范围。 代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode *buildTree(vectorint inorder, vectorint postorder){vectorint indexMap(6000);for (int i 0; i inorder.size(); i){indexMap[inorder[i] 3000] i;}TreeNode *node buildNode(indexMap, postorder, inorder, 0, postorder.size() - 1, 0, inorder.size() - 1);return node;}TreeNode *buildNode(vectorint indexMap, vectorint postorder, vectorint inorder, int postStart, int postEnd, int inStart, int inEnd){int expectValue postorder[postEnd];int index indexMap[expectValue3000];int leftLength index - inStart;int rightLength inEnd - index;TreeNode *root new TreeNode(expectValue);if (leftLength 1){root-left buildNode(indexMap, postorder, inorder, postStart, postStart leftLength - 1, inStart, index - 1);}if (rightLength 1){root-right buildNode(indexMap, postorder, inorder, postEnd - rightLength, postEnd - 1, index 1, inEnd);}return root;}
};
