Java n log n solution, DFS solution


  • 0
    S

    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) {
                leaves.add(node.val);
                
                // 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);
                res.add(leaves);
                if (dummy.left == null) break;
                leaves = new ArrayList<Integer>();
            }
    
            return res;
        }
    }

  • 0

    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


Log in to reply
 

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