-
Notifications
You must be signed in to change notification settings - Fork 0
/
1379 Find a corresponding node of a binary tree in a clone of that tree.c
139 lines (116 loc) · 3.07 KB
/
1379 Find a corresponding node of a binary tree in a clone of that tree.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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
#define NODES 10000
typedef struct
{
int arr[NODES];
int top;
}Stack;
int isStackEmpty(Stack * tmp_stack)
{
if(tmp_stack->top == -1)
return 1;
else
return 0;
}
int isStackFull(Stack * tmp_stack)
{
if(tmp_stack->top == NODES-1)
return 1;
else
return 0;
}
void push(Stack * tmp_stack, int element)
{
if(isStackFull(tmp_stack))
return;
tmp_stack->arr[++(tmp_stack->top)] = element;
}
int pop(Stack * tmp_stack)
{
if(isStackEmpty(tmp_stack))
return -1;
int ret_element = tmp_stack->arr[(tmp_stack->top)];
tmp_stack->top--;
return ret_element;
}
int peek(Stack * tmp_stack, int index)
{
return tmp_stack->arr[index];
}
void original_tree(TreeNode * root, TreeNode * target, Stack * original_stack, bool * target_count)
{
if(root == NULL)
return;
if((*target_count == false) && (root!=target))
{
push(original_stack, root->val);
}
if(root == target)
{
*target_count = true;
return;
}
original_tree(root->left, target, original_stack, target_count);
original_tree(root->right, target, original_stack, target_count);
if(*target_count == false)
{
int pop_element = pop(original_stack);
}
}
void cloned_tree(TreeNode * root, int target, Stack * clone_stack, Stack * original_stack, TreeNode ** ret_node)
{
if(root == NULL)
return;
if(root->val!=target)
{
push(clone_stack, root->val);
}
if(root->val == target)
{
//Analyse the stack, it clone and original stack is same, then it is the target node in clone tree (in case duplicates are allowed)
int i=0;
if(clone_stack->top == original_stack->top)
{
bool match = true;
for(i=0; i<=clone_stack->top; i++)
{
if(peek(clone_stack, i) != peek(original_stack, i))
{
match = false;
break;
}
}
if(match)
{
*ret_node = root;
return;
}
}
}
cloned_tree(root->left, target, clone_stack, original_stack, ret_node);
cloned_tree(root->right, target, clone_stack, original_stack, ret_node);
int pop_element = pop(clone_stack);
}
class Solution {
public:
TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target)
{
Stack original_stack;
original_stack.top = -1;
bool target_found = false;
Stack clone_stack;
clone_stack.top = -1;
original_tree(original, target, &original_stack, &target_found);
TreeNode * ret_node = original;
cloned_tree(cloned, target->val ,&clone_stack, &original_stack, &ret_node);
return ret_node;
}
};