Simple Java recursive 1ms solution


  • 6
    B

    This is pretty straight forward but the general idea is to simply prune the leaves at each iteration of the while loop until the root itself is pruned. We can do this using the x = change(x) paradigm for modifying a tree. Whenever we come across a leaf node, we know we must add it to our result but then we prune it by just returning null.

    public class Solution {
        private TreeNode removeLeaves(TreeNode root, List<Integer> result)
        {
            if (root == null) return null;
            if (root.left == null && root.right == null)
            {
                result.add(root.val);
                return null;
            }
            
            root.left = removeLeaves(root.left, result);
            root.right = removeLeaves(root.right, result);
            return root;
        }
        
        public List<List<Integer>> findLeaves(TreeNode root) {
            List<List<Integer>> results = new ArrayList<List<Integer>>();
            if (root == null) return results;
            
            while (root != null)
            {
                List<Integer> leaves = new ArrayList<Integer>();
                root = removeLeaves(root, leaves);
                results.add(leaves);
            }
            
            return results;
        }
    }

  • 0
    R

    thank you, nice solution


  • -1
    N
    public class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) return list;
        findLeaves(root, list);
        return list;
    }
    
    private int findLeaves(TreeNode node, List<List<Integer>> list) {
        if (isLeaf(node)) {
            addToList(0, list, node.val);
            return 1;
        }
        int l = 0, r = 0;
        if (node.left != null) l = findLeaves(node.left, list);
        if (node.right != null) r = findLeaves(node.right, list);
        int retVal = l>r?l:r;
        node.left = null;
        node.right= null;
        addToList(retVal, list, node.val);
        return (retVal+1);
    }
    
    private void addToList(int index, List<List<Integer>> list, int val) {
        List<Integer> addList;
        if (list.size() > index) {
            addList = list.get(index);
        }
        else {
            addList = new ArrayList<>();
            list.add(addList);
        }
        addList.add(val);
    }
    
    private boolean isLeaf(TreeNode node) {
        return (node.left == null && node.right == null);
    }
    

    }


  • 0
    B

    Clean solution. In worst cases, it can be O(N^2) right?


  • 0
    A

    very good solution. thank you


Log in to reply
 

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