aboutsummaryrefslogtreecommitdiff
path: root/smallest_subtree_deep_node.c
diff options
context:
space:
mode:
Diffstat (limited to 'smallest_subtree_deep_node.c')
-rw-r--r--smallest_subtree_deep_node.c56
1 files changed, 56 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
+}