-
Notifications
You must be signed in to change notification settings - Fork 0
/
105.construct-binary-tree-from-preorder-and-inorder-traversal.c
66 lines (54 loc) · 1.39 KB
/
105.construct-binary-tree-from-preorder-and-inorder-traversal.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/*
* @lc app=leetcode id=105 lang=c
*
* [105] Construct Binary Tree from Preorder and Inorder Traversal
*/
// @lc code=start
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
// first val in pre is root
//bc
if
}
// @lc code=end
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
typedef struct TreeNode TreeNode;
TreeNode *build(int *preorder, int *inorder, int *rootIndex, int inorderLeft, int inorderRight)
{
if (inorderLeft >= inorderRight)
{
return NULL;
}
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
root->val = preorder[*rootIndex];
int mid = 0;
// Finding mid
for (size_t i = inorderLeft; i < inorderRight; i++)
{
if (inorder[i] == preorder[*rootIndex])
{
mid = i;
break;
}
}
(*rootIndex)++;
root->left = build(preorder, inorder, rootIndex, inorderLeft, mid);
root->right = build(preorder, inorder, rootIndex, mid + 1, inorderRight);
return root;
}
struct TreeNode *buildTree(int *preorder, int preorderSize, int *inorder, int inorderSize)
{
int rootIndex = 0;
return build(preorder, inorder, &rootIndex, 0, inorderSize);
}