106. 从中序与后序遍历序列构造二叉树
题目描述:示例:方法
C++Java 通过截图
题目描述:
给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal
示例:示例 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]
class Solution { private: // unordered_mapmap; TreeNode* buildTree(vector & inorder,int iStart,int iEnd,vector & postorder,int pStart,int pEnd){ if(iStart>iEnd) return nullptr; int rootVal=postorder[pEnd]; int rootIdx=-1; for(int i=iStart;i<=iEnd;i++){ if(inorder[i]==rootVal){ rootIdx=i; break; } } int leftLen=rootIdx-iStart; TreeNode* root=new TreeNode(rootVal); root->left=buildTree(inorder,iStart,rootIdx-1,postorder,pStart,pStart+leftLen-1); root->right=buildTree(inorder,rootIdx+1,iEnd,postorder,pStart+leftLen,pEnd-1); return root; } public: TreeNode* buildTree(vector & inorder, vector & postorder) { return buildTree(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1); } };
用unordered_map
int rootIdx=map[rootVal];得到rootVal的索引
class Solution { private: unordered_mapmap; TreeNode* buildTree(vector & inorder,int iStart,int iEnd,vector & postorder,int pStart,int pEnd){ if(iStart>iEnd) return nullptr; int rootVal=postorder[pEnd]; int rootIdx=map[rootVal]; int leftLen=rootIdx-iStart; TreeNode* root=new TreeNode(rootVal); root->left=buildTree(inorder,iStart,rootIdx-1,postorder,pStart,pStart+leftLen-1); root->right=buildTree(inorder,rootIdx+1,iEnd,postorder,pStart+leftLen,pEnd-1); return root; } public: TreeNode* buildTree(vector & inorder, vector & postorder) { for(int i=0;i Java class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { return buildTree(inorder,0,inorder.length-1,postorder,0,postorder.length-1); } TreeNode buildTree(int[] inorder,int iStart,int iEnd,int[] postorder,int pStart,int pEnd){ if(iStart>iEnd) return null; int rootVal=postorder[pEnd]; int rootIdx=-1; for(int i=iStart;i<=iEnd;i++){ if(inorder[i]==rootVal){ rootIdx=i; break; } } int leftLen=rootIdx-iStart; TreeNode root=new TreeNode(rootVal); root.left=buildTree(inorder,iStart,rootIdx-1,postorder,pStart,pStart+leftLen-1); root.right=buildTree(inorder,rootIdx+1,iEnd,postorder,pStart+leftLen,pEnd-1); return root; } }用Map
idx_map=new HashMap<>();
int rootIdx=idx_map.get(rootVal);得到rootVal的索引class Solution { Map通过截图idx_map=new HashMap<>(); public TreeNode buildTree(int[] inorder, int[] postorder) { for(int i=0;i iEnd) return null; int rootVal=postorder[pEnd]; int rootIdx=idx_map.get(rootVal); int leftLen=rootIdx-iStart; TreeNode root=new TreeNode(rootVal); root.left=buildTree(inorder,iStart,rootIdx-1,postorder,pStart,pStart+leftLen-1); root.right=buildTree(inorder,rootIdx+1,iEnd,postorder,pStart+leftLen,pEnd-1); return root; } } 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)