二叉树]leetcode105:从前序与中序遍历序列构造二叉树(medium)"/>
[二叉树]leetcode105:从前序与中序遍历序列构造二叉树(medium)
题目:
题解:可参考从中序与后序遍历序列构造二叉树
/*** 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) {if(preorder.empty()||inorder.empty()) return nullptr;TreeNode *root=new TreeNode(*preorder.begin());//前序数组的第一个元素为根节点auto it=find(inorder.begin(),inorder.end(),*preorder.begin());//在中序数组中寻找指向根节点的迭代器vector<int> iLeft(inorder.begin(),it),iRight(it+1,inorder.end());//左右子树中序数组int size=iLeft.size();vector<int> pLeft(preorder.begin()+1,preorder.begin()+1+size),pRight(preorder.begin()+1+size,preorder.end());//左右子树前序数组root->left=buildTree(pLeft,iLeft);root->right=buildTree(pRight,iRight);return root;}
};
更多推荐
[二叉树]leetcode105:从前序与中序遍历序列构造二叉树(medium)
发布评论