diff options
author | Jack Sangdahl <[email protected]> | 2024-08-22 14:34:25 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-08-22 14:34:25 -0600 |
commit | 515d837f3d923eb5c360386e0ae03a31ddcea9b0 (patch) | |
tree | e0dfedf87b174869c7bc28171a00489913ccc423 | |
parent | 77f46021e62b1d16803e746db4a39d22d17700e2 (diff) | |
download | leetcode-515d837f3d923eb5c360386e0ae03a31ddcea9b0.tar.gz leetcode-515d837f3d923eb5c360386e0ae03a31ddcea9b0.zip |
865. smallest subtree with all the deepest nodes
-rw-r--r-- | smallest_subtree_deep_node.c | 56 | ||||
-rw-r--r-- | smallest_subtree_deep_node.py | 46 |
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])) |