diff options
Diffstat (limited to 'smallest_subtree_deep_node.c')
-rw-r--r-- | smallest_subtree_deep_node.c | 56 |
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 +} |