Python DFS, remove the leaf


  • 0
    class Solution(object):
        def findLeaves(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[int]]
            """
            def dfs(node, parent, label, res):
                if node:
                    leaf = False
                    if not node.left and not node.right:
                        res.append(node.val)
                        leaf = True
                    dfs(node.left, node, "left", res)
                    dfs(node.right, node, "right", res)
                    if leaf:
                        if label == "left": parent.left = None
                        if label == "right": parent.right = None
            finalres = []
            while root:
                if not root.left and not root.right:
                    finalres.append([root.val])
                    break
                res = []
                dfs(root, None, None, res)
                finalres.append(res)
            return finalres
    

    The idea is quite simple: for each traversal, save all the values of leaves and remove them.


Log in to reply
 

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