这道题目前前后后做了好几遍,但是每一次都害怕写错了细节,所以多复习几遍准没错~
首先我们要烂熟于心:前序:根左右;中序:左根右;后续:左右根
那么,前序 + 中序就可以唯一确定一棵树,首先由前序确定根结点的值,然后中序找出根结点的位置,确定左右子树的结点个数;接着就可以采用递归思路求解了;
中序 + 后续也是一样,首先由后序确定根结点的值,然后中序找出根结点的位置,确定左右子树的结点个数;接着就可以采用递归思路求解了;
前序 + 中序
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { private: unordered_map<int, int> dp;//用于更快的查找根结点 TreeNode* recur(vector<int> pre, vector<int> vin, int lPre,\ int rPre, int lVin, int rVin) { //边界 if (lPre > rPre) return nullptr; // TreeNode* node = new TreeNode(pre[lPre]); int lenLeft = dp[pre[lPre]] - lVin; int lenRight = rVin -dp[pre[lPre]]; node->left = recur(pre, vin, lPre + 1, lPre + lenLeft, lVin, lVin + lenLeft - 1); node->right = recur(pre, vin, lPre + lenLeft + 1, rPre, lVin + lenLeft + 1, rVin); return node; } public: TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { //前序确定根结点的值,中序确定左右子树的部分,然后递归 int len = pre.size(); for (int i = 0; i < vin.size(); ++i) dp[vin[i]] = i; return recur(pre, vin, 0, len - 1, 0, len - 1); } };
中序 + 后续
/** * 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 { private: unordered_map<int,int> mp; TreeNode* dfs(vector<int>& inorder, vector<int>& postorder,int in_left,int in_right,int post_left,int post_right){ //由后序遍历可以得到根节点,然后可以从中序遍历得到左右子树的组成; if(in_left>in_right) return nullptr; //算出左子树长度 int len_left=mp[postorder[post_right]]-in_left; TreeNode* root=new TreeNode(postorder[post_right]); root->left=dfs(inorder,postorder,in_left,in_left+len_left-1,post_left,post_left+len_left-1); root->right=dfs(inorder,postorder,in_left+len_left+1,in_right,post_left+len_left,post_right-1); return root; } public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { int len=inorder.size(); for(int i=0;i<len;++i) mp[inorder[i]]=i; return dfs(inorder,postorder,0,len-1,0,len-1); } };