algorithms-python/algorithms/tree/min_height.py at master · ivan1911/algorithms-python · GitHub

History

54 lines (45 loc) · 1.29 KB

Raw

from tree import TreeNode

def min_depth(self, root):

"""

:type root: TreeNode

:rtype: int

"""

if root is None:

return 0

if root.left is not None or root.right is not None:

return max(self.minDepth(root.left), self.minDepth(root.right))+1

return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

# iterative

def min_height(root):

if root is None:

return 0

height = 0

level = [root]

while level:

height += 1

new_level = []

for node in level:

if node.left is None and node.right is None:

return height

if node.left is not None:

new_level.append(node.left)

if node.right is not None:

new_level.append(node.right)

level = new_level

return height

def print_tree(root):

if root is not None:

print(root.val)

print_tree(root.left)

print_tree(root.right)

if __name__ == '__main__':

tree = TreeNode(10)

tree.left = TreeNode(12)

tree.right = TreeNode(15)

tree.left.left = TreeNode(25)

tree.left.left.right = TreeNode(100)

tree.left.right = TreeNode(30)

tree.right.left = TreeNode(36)

height = min_height(tree)

print_tree(tree)

print("height:", height)

algorithms-python/algorithms/tree/min_height.py at master · ivan1911/algorithms-python · GitHub

Expand file tree

Breadcrumbs

min_height.py

Latest commit

History

Breadcrumbs

min_height.py

File metadata and controls