Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.
Example:
Given binary tree
1
/
2 3
/
4 5
Returns [4, 5, 3], [2], [1].
Explanation:
- Removing the leaves [4, 5, 3] would result in this tree:
1
/
2
- Now removing the leaf [2] would result in this tree:
1
- Now removing the leaf [1] would result in the empty tree:
[]
Returns [4, 5, 3], [2], [1].
Python Solution:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def findLeaves(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
res = []
def postorder(root):
if not root: return -1
left = postorder(root.left)
right = postorder(root.right)
cur = max(left, right) + 1
if cur == len(res):
res.append([])
res[cur].append(root.val)
return cur
postorder(root)
return res
Summary:
- from bottom to up
LeetCode: 366. Find Leaves of Binary Tree
近期评论