Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
C Solution 1:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
if (!preorderSize) return 0;
struct TreeNode *root = malloc(sizeof(struct TreeNode));
root->val = preorder[0];
int i;
for (i = 0; i < inorderSize && inorder[i] != preorder[0]; i++);
root->left = buildTree(preorder + 1, i, inorder, i);
root->right = buildTree(preorder + 1 + i, preorderSize - 1 - i, inorder + i + 1, inorderSize - i - 1);
return root;
}
C Solution 2:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
if (preorderSize < 1) return 0;
struct TreeNode *root = malloc(sizeof(struct TreeNode)), *cur = root;
root->val = preorder[0];
root->left = 0;
root->right = 0;
struct TreeNode **stack = malloc(preorderSize * sizeof(struct TreeNode *));
stack[0] = root;
int top = 1, i, j = 0, isright = 0;
for (i = 1; i < preorderSize; i++) {
while (top && stack[top - 1]->val == inorder[j]) {
cur = stack[--top];
isright = 1;
j++;
}
struct TreeNode *child = malloc(sizeof(struct TreeNode));
child->val = preorder[i];
child->left = 0;
child->right = 0;
stack[top++] = child;
if (isright) {
cur->right = child;
isright = 0;
}
else {
cur->left = child;
}
cur = child;
}
return root;
}
Summary:
- Solution 2 works, but I don't understand thoroughly, and the complexity is O(n).
LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal
近期评论