[二叉树]leetcode106：从中序与后序遍历构造二叉树(medium)

二叉树]leetcode106：从中序与后序遍历构造二叉树(medium)"/>

[二叉树]leetcode106：从中序与后序遍历构造二叉树(medium)

题目：

解题思路：

• 1）后序数组的最后一个元素为根节点，根据根节点可将中序数组划分为左子树中序列表和右子树中序数组
• 2）又因为一棵树的中序数组长度与后序数组长度大小相同，所以可以根据长度划分后序数组为左右子树后序数组
• 3）对于根的左右结点，递归调用即可

/*** 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>& inorder, vector<int>& postorder) {if(inorder.empty()||postorder.empty()) return nullptr;//后序数组的最后一个元素为根结点 TreeNode* root=new TreeNode(*postorder.rbegin());//在中序数组中找到指向根节点的迭代器，用于划分左右子树 auto it=find(inorder.begin(),inorder.end(),*postorder.rbegin());//根据根结点将中序数组划分为左子树中序数组，右子树中序数组 vector<int> iLeft(inorder.begin(),it),iRight(it+1,inorder.end());//由于树的中序和后序长度一样，所以根据长度划分后序数组为左右子树后序数组 int size=iLeft.size(); vector<int> pLeft(postorder.begin(),postorder.begin()+size),pRight(postorder.begin()+size,postorder.end()-1); root->left=buildTree(iLeft,pLeft);   root->right=buildTree(iRight,pRight);   return root;}
};