ac solution code


  • 0
     Solution1. DFS - time = O(n^2); space = O(n^2)
     Group nodes with its height(distance to deepest leaf):
    
     1. Remove:
            Remove nodes in res[h] level by level
     2. BFS doesn't work, because height is different from tree level. height['5'] = 0, height['3'] = 0
          1
         / \
        2   3
       / \     
      4   5     
    
     Q: is time complexity to tree DFS = n^2 (Not n1: because there're no (i-1) branches for each node i, as in permutation)
     Say height = node's distance from deepest leaf (not bottom)
    
     1) bottom up
     2) get height of each node
     3) res[h] = array of (nodeHeigh == h)
    
        func findLeaves(_ root: TreeNode?) -> [[Int]] {
            var res: [[Int]] = []
            height(root, &res)
            return res
        }
        
        @discardableResult
        private func height(_ node: TreeNode?, _ res: inout [[Int]]) -> Int {
            guard let node = node else {return -1}
            let leftHeight = height(node.left, &res)
            let rightHeight = height(node.right, &res)
            let curHeight = 1 + max(leftHeight, rightHeight)    // height: node's distance to its deepest leaf
            if leftHeight == 0 { node.left = nil }              // Remove leaves, whose height from bottom is 0
            if rightHeight == 0 { node.right = nil }
            
            if (curHeight > res.count - 1) {                   // Init a new level
                res.append([])
            }
            res[curHeight].append(node.val)                    // Append current node to the array corresponding to its height
            return curHeight
        }
    

Log in to reply
 

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