# Java n log n solution, DFS solution

• The idea is to do DFS and remove the leaf node. DFS the whole tree take n steps and we need to repeat it for the depth of the tree which is log n so the total time complexity is n log n. In order to remove the node, the DFS function takes parent of the node as an argument.

``````public class Solution {
private void find(TreeNode parent, TreeNode node, List<Integer> leaves) {
if (node.left == null && node.right == null) {

// remove the leaf node from the tree
if (parent.left == node)
parent.left = null;
if (parent.right == node)
parent.right = null;
return;
}

if (node.left != null)
find(node, node.left, leaves);

if (node.right != null)
find(node, node.right, leaves);
}

public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (root == null) return res;

TreeNode dummy = new TreeNode(0);
dummy.left = root;
List<Integer> leaves = new ArrayList<Integer>();

while (true) {
// remove layer by layer
find(dummy, root, leaves);
if (dummy.left == null) break;
leaves = new ArrayList<Integer>();
}

return res;
}
}``````

• depth of the tree which is log n so the total time complexity is n log n

depth of the tree which is n so the total time complexity is n2

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