aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-04-03 21:09:12 -0600
committerJack Sangdahl <[email protected]>2025-04-03 21:09:12 -0600
commit6e2b4dac24efabc44781551afdb9d1723849ae62 (patch)
treee98a2cda976e0df98fee1190172e8c88632fb49d
parente65bc03220db2853eef8cd5ded9d69723014e6f4 (diff)
downloadleetcode-6e2b4dac24efabc44781551afdb9d1723849ae62.tar.gz
leetcode-6e2b4dac24efabc44781551afdb9d1723849ae62.zip
1123. lowest common ancestor of deepest leaves
-rw-r--r--low_common_ancestor_leaf.c49
-rw-r--r--low_common_ancestor_leaf.py48
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))