目录
一:题目:
二:代码:
三:结果:
一:题目:
给定两个整数数组 inorder
和 postorder
,其中 inorder
是二叉树的中序遍历, postorder
是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。
二:代码:
/*** 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:TreeNode* travsal(vector<int>& inorder,vector<int>& postorder){if(postorder.size()==0) return NULL;int rootvalue=postorder[postorder.size()-1];TreeNode* root=new TreeNode(rootvalue);if(postorder.size()==1) return root;int sum;for( sum=0;sum<inorder.size();sum++){if(inorder[sum]==rootvalue){break;}}vector<int> leftinorder(inorder.begin(),inorder.begin()+sum);vector<int> rightinorder(inorder.begin()+1+sum,inorder.end());postorder.resize(postorder.size()-1);vector<int> leftpostorder(postorder.begin(),postorder.begin()+leftinorder.size());vector<int> rightpostorder(postorder.begin()+leftinorder.size(),postorder.end());root->left=travsal(leftinorder,leftpostorder);root->right=travsal(rightinorder,rightpostorder);return root;}
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(inorder.size()==0||postorder.size()==0) return NULL;return travsal(inorder,postorder);}
};