aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-08-22 14:34:25 -0600
committerJack Sangdahl <[email protected]>2024-08-22 14:34:25 -0600
commit515d837f3d923eb5c360386e0ae03a31ddcea9b0 (patch)
treee0dfedf87b174869c7bc28171a00489913ccc423
parent77f46021e62b1d16803e746db4a39d22d17700e2 (diff)
downloadleetcode-515d837f3d923eb5c360386e0ae03a31ddcea9b0.tar.gz
leetcode-515d837f3d923eb5c360386e0ae03a31ddcea9b0.zip
865. smallest subtree with all the deepest nodes
-rw-r--r--smallest_subtree_deep_node.c56
-rw-r--r--smallest_subtree_deep_node.py46
2 files changed, 102 insertions, 0 deletions
diff --git a/smallest_subtree_deep_node.c b/smallest_subtree_deep_node.c
new file mode 100644
index 0000000..108ce05
--- /dev/null
+++ b/smallest_subtree_deep_node.c
@@ -0,0 +1,56 @@
+// 865. Smallest Subtree with all the Deepest Nodes
+#include "leetcode.h"
+
+/*
+ * given the 'root' of a binary tree, the depth of each node is the shortest
+ * distance to the root. return the smallest subtree such that it contains all
+ * the deepest nodes in the original tree. a node is called the deepest if it
+ * has the largest depth possible among any node in the entire tree. the
+ * subbtree of a node is a tree consisting of that node, plus the set of all
+ * 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;
+}
+
+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 TreeNode *subtreeWithAllDeepest(struct TreeNode *root) {
+ int height = tree_height(root);
+ struct TreeNode *lca = NULL;
+ tree_lca(root, height, 1, &lca);
+ return lca;
+}
+
+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
+}
diff --git a/smallest_subtree_deep_node.py b/smallest_subtree_deep_node.py
new file mode 100644
index 0000000..a06eeea
--- /dev/null
+++ b/smallest_subtree_deep_node.py
@@ -0,0 +1,46 @@
+# 865. Smallest Subtree with all the Deepest Nodes
+
+"""
+given the 'root' of a binary tree, the depth of each node is the shortest
+distance to the root. return the smallest subtree such that it contains all
+the deepest nodes in the original tree. a node is called the deepest if it
+has the largest depth possible among any node in the entire tree. the
+subbtree of a node is a tree consisting of that node, plus the set of all
+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):
+ """
+ :type root: TreeNode
+ :rtype: TreeNode
+ """
+
+ def dfs(root):
+ if not root:
+ 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
+
+ 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]))