1.题目:
输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
限制:
0 <= 节点个数 <= 5000
2. 分析与代码:
重构二叉树看另一篇博客:重构二叉树 + 输出 (层序遍历、其他遍历) - 湘summer - 博客园 (cnblogs.com)
代码:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { return getBinaryTree(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1); } TreeNode* getBinaryTree(vector<int>& preorder,int preBegin,int preEnd,vector<int>& inorder,int inBegin,int inEnd){ if(preBegin > preEnd) return NULL; TreeNode* tree = new TreeNode(preorder[preBegin]); // *tree = (preorder[preBegin],NULL,NULL); int r = findRootInInorder(inorder,inBegin,inEnd,preorder[preBegin]); int count = r-inBegin; //inBegin从0开始,无需加1 if(r!=inBegin) tree->left = getBinaryTree(preorder,preBegin+1,preBegin+count,inorder,inBegin,r-1); if(r!=inEnd) tree->right = getBinaryTree(preorder,preBegin+count+1,preEnd,inorder,r+1,inEnd); return tree; } int findRootInInorder(vector<int>& inorder,int inBegin,int inEnd,int key){ for(int i=inBegin;i<=inEnd;i++){ if(inorder[i] == key) return i; } return 0; } };
也可以用hashMap去查找根节点在中序遍历中的位置。
标签:preorder,TreeNode,07,Offer,int,inBegin,二叉树,inorder,preBegin From: https://www.cnblogs.com/lxpblogs/p/16586244.html