Python solution that actually remove the leaves from the tree


  • 3
    S

    I thought we need to actually remove all the leaves so that's what my code below does.
    According to other's solutions it looks like we don't need to remove the leaves from the tree but only group leaves by level.
    Anyway, I'm posting my code for actually removing leaves from the tree level by level using DFS. its time complexity is higher than others' solution but still PASS the the OJ.

    class Solution(object):
        
        def findLeaves(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[int]]
            """
            
            if not root:
                return []
            result=[]
            while root:
                curLeaves = []
                root = self._findLeaves(root, curLeaves)
                
                result.append(curLeaves)
            
            return result 
    
        def _findLeaves(self, root, curLeaves):
            if not root:
                return None
            if not root.left and not root.right:
                curLeaves.append(root.val)
                return None
            else:
                root.left = self._findLeaves(root.left, curLeaves)
                root.right = self._findLeaves(root.right, curLeaves)
                return root

  • 0

    This is the most straightforward way to solve this problem but highly not recommended due to its high time complexity.


  • 0
    R

    I have similar solution, but my time complexity is only 38 ms average, beating 76%

    class Solution(object):
        def findLeaves(self, root):
            self.cp = []
            self.res = []
            
            def helper(node):
                if not node.left and not node.right:
                    self.cp.append(node.val)
                    return -1
                if node.left is not None:
                    vs = helper(node.left)
                    if vs == -1:
                        node.left = None
                if node.right is not None:
                    vs = helper(node.right)
                    if vs == -1:
                        node.right = None
                return 1
            
            while root is not None:
                vs = helper(root)
                self.res.append(self.cp)
                self.cp = []
                if vs == -1:
                    break
            return self.res
    

Log in to reply
 

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