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
|
// 1123. Lowest Common Ancestor of Deepest Leaves
#include "leetcode.h"
/*
* given the 'root' of a binary tree, return the lowest common ancestor of its
* deepest leaves. recall that the node of a binary tree is a leaf if and only
* if it has no children, the depth of the root of the tree is 0. if the depth
* of a node is 'd', the depth of each of its children is 'd + 1'. and the
* lowest common ancestor of a set 's' is the node 'a' with the largest depth
* such that every node in 's' is in the subtree with root 'a'.
*/
int depth(struct TreeNode *root) {
if (!root)
return 0;
int l = depth(root->left);
int r = depth(root->right);
return l > r ? l + 1 : r + 1;
}
struct TreeNode *lcaDeepestLeaves(struct TreeNode *root) {
if (!root)
return NULL;
int l = depth(root->left);
int r = depth(root->right);
if (l == r)
return root;
return l > r ? lcaDeepestLeaves(root->left) : lcaDeepestLeaves(root->right);
}
int main() {
int r1i[] = {3, 5, 1, 6, 2, 0, 8, -1, -1, 7, 4}, r2i[] = {1},
r3i[] = {0, 1, 3, -1, 2};
struct TreeNode *r1 = treenode_build(r1i, ARRAY_SIZE(r1i));
struct TreeNode *r2 = treenode_build(r2i, ARRAY_SIZE(r2i));
struct TreeNode *r3 = treenode_build(r3i, ARRAY_SIZE(r3i));
struct TreeNode *lcadl1 = lcaDeepestLeaves(r1);
struct TreeNode *lcadl2 = lcaDeepestLeaves(r2);
struct TreeNode *lcadl3 = lcaDeepestLeaves(r3);
treenode_print(lcadl1); // expect: 2 7 4
printf("\n");
treenode_print(lcadl2); // expect: 1
printf("\n");
treenode_print(lcadl3); // expect: 2
printf("\n");
treenode_free(r1);
treenode_free(r2);
treenode_free(r3);
}
|