diff options
Diffstat (limited to 'smallest_subtree_deep_node.py')
-rw-r--r-- | smallest_subtree_deep_node.py | 46 |
1 files changed, 46 insertions, 0 deletions
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])) |