diff options
author | Jack Sangdahl <[email protected]> | 2025-04-03 21:09:12 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-04-03 21:09:12 -0600 |
commit | 6e2b4dac24efabc44781551afdb9d1723849ae62 (patch) | |
tree | e98a2cda976e0df98fee1190172e8c88632fb49d | |
parent | e65bc03220db2853eef8cd5ded9d69723014e6f4 (diff) | |
download | leetcode-6e2b4dac24efabc44781551afdb9d1723849ae62.tar.gz leetcode-6e2b4dac24efabc44781551afdb9d1723849ae62.zip |
1123. lowest common ancestor of deepest leaves
-rw-r--r-- | low_common_ancestor_leaf.c | 49 | ||||
-rw-r--r-- | low_common_ancestor_leaf.py | 48 |
2 files changed, 97 insertions, 0 deletions
diff --git a/low_common_ancestor_leaf.c b/low_common_ancestor_leaf.c new file mode 100644 index 0000000..87b5bf4 --- /dev/null +++ b/low_common_ancestor_leaf.c @@ -0,0 +1,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); +} diff --git a/low_common_ancestor_leaf.py b/low_common_ancestor_leaf.py new file mode 100644 index 0000000..4b0036f --- /dev/null +++ b/low_common_ancestor_leaf.py @@ -0,0 +1,48 @@ +# 1123. Lowest Common Ancestor of Deepest Leaves +import leetcode + +""" +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'. +""" + + +class Solution(object): + def lcaDeepestLeaves(self, root): + """ + :type root: Optional[TreeNode] + :rtype: Optional[TreeNode] + """ + + def depth(node): + if not node: + return 0 + return max(depth(node.left), depth(node.right)) + 1 + + def dfs(node, m, n): + if not node: + return None + if m - 1 == n: + return node + l = dfs(node.left, m, n + 1) + r = dfs(node.right, m, n + 1) + if l and r: + return node + return l if l else r + + m = depth(root) + return dfs(root, m, 0) + + +if __name__ == "__main__": + obj = Solution() + r1 = leetcode.treenode_build(root=[3, 5, 1, 6, 2, 0, 8, None, None, 7, 4]) + r2 = leetcode.treenode_build(root=[1]) + r3 = leetcode.treenode_build(root=[0, 1, 3, None, 2]) + print(obj.lcaDeepestLeaves(r1)) + print(obj.lcaDeepestLeaves(r2)) + print(obj.lcaDeepestLeaves(r3)) |