LeetCode Week 5
105. Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
solutions:
本题意是要求根据输入的前序和中序遍历来确定一颗唯一的二叉树。
由前序遍历的要求我们可知,前序遍历的第一个元素一定是二叉树的根,且题目说了数组中无重复元素,由此我们可以在中序数组中找到这个元素,并以此为分节点,左边则是中序遍历的左子树,右边则是中序遍历的右子树。之后便可根据中序的左右子树确定前序遍历的左右部分。接着递归左右子树,最后得到一颗唯一的二叉树。
/**
* 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) {
return buildtree(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
}
TreeNode* buildtree(vector<int>& preorder, int pleft, int pright, vector<int>& inorder, int ileft, int iright) {
if(pleft > pright || ileft > iright) {
return NULL;
}
int i = 0;
for(i = ileft; i <= iright; i++) {
if (preorder[pleft] == inorder[i]) {
break;
}
}
TreeNode *root = new TreeNode(preorder[pleft]);
root->left = buildtree(preorder, pleft + 1, pleft + i - ileft, inorder, ileft, i - 1);
root->right = buildtree(preorder, pleft + i - ileft + 1, pright, inorder, i + 1, iright);
return root;
}
};