# ac solution code

• `````` 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
}

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
}
``````

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