Simple Python solution using Preorder Traversal


  • 0
    P

    Idea — in a preorder traversal check if the node is a leaf. If the current node is leaf, add it's value to the list and delete the node using it's parent. Base cases: 1. if the current node is null -> simply return; 2. If the current node is root, i.e. parent == child, nullify the root and stop.

    Keep deleting leaves until the root is valid (also create an empty list in the result array after every iteration).

    # Definition for a binary tree node.
    class TreeNode(object):
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
        def __repr__(self):
            return str(self.val)
    
    class Solution(object):
        def findLeaves(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[int]]
            """
            l = [[]]
            def helperDeleteLeaves(parent, child):
                if not child:
                    return
                if not child.left and not child.right:
                    if parent.left == child:
                        l[-1].append(child.val)
                        parent.left = None
                    elif parent.right == child:
                        l[-1].append(child.val)
                        parent.right = None
                    elif parent == child:
                        l[-1].append(child.val)
                        self.root = None
                        return
                helperDeleteLeaves(child, child.left)
                helperDeleteLeaves(child, child.right)
    
            self.root = root
            while self.root:
                helperDeleteLeaves(self.root, self.root)
                l.append([])
            l = l[:-1]
            return l

Log in to reply
 

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