-
Notifications
You must be signed in to change notification settings - Fork 0
/
1123 Lowest Common Ancestor of Deepest Leaves.c
98 lines (77 loc) · 2.14 KB
/
1123 Lowest Common Ancestor of Deepest Leaves.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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int find_height(struct TreeNode * root)
{
if(root == NULL)
return 0;
int left = find_height(root->left);
int right = find_height(root->right);
if(left >= right)
return (left + 1);
else
return (right+1);
}
void find_deepest_node(struct TreeNode * root, int cur_ht, int max_ht, bool * found)
{
if(root == NULL)
return;
if(cur_ht == max_ht)
{
*found = true;
return;
}
find_deepest_node(root->left, cur_ht+1, max_ht, found);
find_deepest_node(root->right, cur_ht+1, max_ht, found);
}
void preorder(struct TreeNode * root, int height, int cur_ht, struct TreeNode ** common)
{
if(root == NULL)
return;
//If the nodes has the deepest leaves on both subtrees then the node itself is the common ancestor
bool left_found = false;
bool right_found = false;
find_deepest_node(root->left, cur_ht+1, height, &left_found);
find_deepest_node(root->right, cur_ht+1, height, &right_found);
if((left_found==true) && (right_found==true))
{
*common = root;
return;
}
else
{
if(*common == NULL)
preorder(root->left, height, cur_ht+1, common);
if(*common == NULL)
preorder(root->right, height, cur_ht+1, common);
}
}
void find_deep_leaf_addr(struct TreeNode * root, int height, int cur_ht, struct TreeNode ** common)
{
if(root == NULL)
return;
if(cur_ht == height)
{
*common = root;
return;
}
find_deep_leaf_addr(root->left, height, cur_ht+1, common);
find_deep_leaf_addr(root->right, height, cur_ht+1, common);
}
struct TreeNode* lcaDeepestLeaves(struct TreeNode* root)
{
int height = find_height(root);
struct TreeNode * common = NULL;
int cur_ht = 1;
preorder(root, height, cur_ht, &common);
if(common == NULL)
{
find_deep_leaf_addr(root, height, cur_ht, &common);
}
return common;
}