二叉树]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;}
};
更多推荐
[二叉树]leetcode106:从中序与后序遍历构造二叉树(medium)
发布评论