leetcode

commit 88b59de23f7bea33a9ff2867bef3da09632750e5
parent 1eeafe17151a78d6a7a5d6b079378e176dfc95c4
Author: Jack Sangdahl <jack@pngu.org>
Date:   Thu,  8 Jan 2026 22:10:23 -0700

865. smallest subtree with all the deepest nodes

Diffstat:
M
smallest_subtree_deep_node.c
 | 
69
+++++++++++++++++++++++++++++++++------------------------------------
M
smallest_subtree_deep_node.py
 | 
36
++++++++++++++++--------------------

2 files changed, 49 insertions(+), 56 deletions(-)
diff --git a/smallest_subtree_deep_node.c b/smallest_subtree_deep_node.c
@@ -10,47 +10,44 @@
  * descendants of that node
  */
 
-int tree_height(struct TreeNode *root) {
-  if (root) {
-    int l = tree_height(root->left), r = tree_height(root->right);
-    return l >= r ? l + 1 : r + 1;
-  }
-  return 0;
-}
+struct pair {
+  int depth;
+  struct TreeNode *node;
+};
 
-bool tree_lca(struct TreeNode *root, int tree_height, int curr,
-              struct TreeNode **lca) {
-  if (root) {
-    bool l = tree_lca(root->left, tree_height, curr + 1, lca);
-    bool r = tree_lca(root->right, tree_height, curr + 1, lca);
-    if (curr == tree_height) {
-      *lca = root;
-      return true;
-    }
-    if (l && r)
-      *lca = root;
-    return l || r;
-  }
-  return false;
+struct pair dfs(struct TreeNode *root) {
+  if (!root)
+    return (struct pair){0, NULL};
+  struct pair l = dfs(root->left);
+  struct pair r = dfs(root->right);
+  if (l.depth > r.depth)
+    return (struct pair){l.depth + 1, l.node};
+  if (r.depth > l.depth)
+    return (struct pair){r.depth + 1, r.node};
+  return (struct pair){l.depth + 1, root};
 }
 
 struct TreeNode *subtreeWithAllDeepest(struct TreeNode *root) {
-  int height = tree_height(root);
-  struct TreeNode *lca = NULL;
-  tree_lca(root, height, 1, &lca);
-  return lca;
+  return dfs(root).node;
 }
 
 int main() {
-  struct TreeNode *root = treenode_create(3);
-  root->left = treenode_create(5);
-  root->left->left = treenode_create(6);
-  root->left->right = treenode_create(2);
-  root->left->right->left = treenode_create(7);
-  root->left->right->right = treenode_create(4);
-  root->right = treenode_create(1);
-  root->right->left = treenode_create(0);
-  root->right->right = treenode_create(8);
-  struct TreeNode *res = subtreeWithAllDeepest(root);
-  treenode_print(res); // expect: 7 2 4
+  int r1i[] = {3, 5, 1, 6, 2, 0, 8, -1, -1, 7, 4};
+  int r2i[] = {1};
+  int 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 *stwad1 = subtreeWithAllDeepest(r1);
+  struct TreeNode *stwad2 = subtreeWithAllDeepest(r1);
+  struct TreeNode *stwad3 = subtreeWithAllDeepest(r1);
+  treenode_print(stwad1); // expect: 2 7 4
+  treenode_print(stwad2); // expect: 1
+  treenode_print(stwad3); // expect: 2
+  treenode_free(r1);
+  treenode_free(r2);
+  treenode_free(r3);
+  treenode_free(stwad1);
+  treenode_free(stwad2);
+  treenode_free(stwad3);
 }
diff --git a/smallest_subtree_deep_node.py b/smallest_subtree_deep_node.py
@@ -1,4 +1,5 @@
 # 865. Smallest Subtree with all the Deepest Nodes
+import leetcode
 
 """
 given the 'root' of a binary tree, the depth of each node is the shortest
@@ -10,14 +11,6 @@ descendants of that node
 """
 
 
-# Definition for a binary tree node.
-class TreeNode(object):
-    def __init__(self, val=0, left=None, right=None):
-        self.val = val
-        self.left = left
-        self.right = right
-
-
 class Solution(object):
     def subtreeWithAllDeepest(self, root):
         """
@@ -25,22 +18,25 @@ class Solution(object):
         :rtype: TreeNode
         """
 
-        def dfs(root):
-            if not root:
+        def dfs(node):
+            if not node:
                 return 0, None
-            l, r = dfs(root.left), dfs(root.right)
-            if l[0] > r[0]:
-                return l[0] + 1, l[1]
-            elif l[0] < r[0]:
-                return r[0] + 1, r[1]
-            else:
-                return l[0] + 1, root
+            ld, ln = dfs(node.left)
+            rd, rn = dfs(node.right)
+            if ld > rd:
+                return ld + 1, ln
+            if rd > ld:
+                return rd + 1, rn
+            return ld + 1, node
 
         return dfs(root)[1]
 
 
 if __name__ == "__main__":
     obj = Solution()
-    print(obj.subtreeWithAllDeepest(root=[3, 5, 1, 6, 2, 0, 8, None, None, 7, 4]))
-    print(obj.subtreeWithAllDeepest(root=[1]))
-    print(obj.subtreeWithAllDeepest(root=[0, 1, 3, None, 2]))
+    r1 = leetcode.treenode_build(vals=[3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
+    r2 = leetcode.treenode_build(vals=[1])
+    r3 = leetcode.treenode_build(vals=[0, 1, 3, None, 2])
+    print(obj.subtreeWithAllDeepest(r1))
+    print(obj.subtreeWithAllDeepest(r2))
+    print(obj.subtreeWithAllDeepest(r3))