Simple Python solution with explaination


  • 0

    I write a helper function to extract leaves from the tree and save them in the res until it hit the root.

    class Solution(object):
        def findLeaves(self, root):
            if not root:
                return []
            res = [] 
            self.helper(root, res)
            return res
    
        def helper(self, root, res): # simple bfs
            # (node, parent, left or right child of it's parent)
            s = [(root, None, 'root')] 
            cur = []
            while s:
                tmp = s.pop(0)
                node, parent = tmp[0], tmp[1]
                if node.left:
                    s.append((node.left,node,'left'))
                if node.right:
                    s.append((node.right,node,'right'))
                # if it is leaf do it's parent
                if not node.left and not node.right:
                    cur.append(node.val)
                    if tmp[2]=='left':
                        parent.left = None
                    elif tmp[2]=='right':
                        parent.right = None
            # recurse untill hit the root
            if cur!= [root.val]:
                res.append(cur)
                self.helper(root, res)
            else:
                res.append(cur)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.