1 ms Easy understand Java Solution


  • 20
    G
    public class Solution {
        public List<List<Integer>> findLeaves(TreeNode root) {
            
            List<List<Integer>> leavesList = new ArrayList< List<Integer>>();
            List<Integer> leaves = new ArrayList<Integer>();
            
            while(root != null) {
                if(isLeave(root, leaves)) root = null;
                leavesList.add(leaves);
                leaves = new ArrayList<Integer>();
            }
            return leavesList;
        }
        
        public boolean isLeave(TreeNode node, List<Integer> leaves) {
            
            if (node.left == null && node.right == null) {
                leaves.add(node.val);
                return true;
            }
            
            if (node.left != null) {
                 if(isLeave(node.left, leaves))  node.left = null;
            }
            
            if (node.right != null) {
                 if(isLeave(node.right, leaves)) node.right = null;
            }
            
            return false;
        }
    }

  • 0
    I

    Same as my resolution.
    In worst case, this will be O(n^2)


  • 0
    L

    By assigning the node to null, the original structure of tree is destroyed, although it could work.


  • 0
    L

    same idea
    but what's wrong with my code?

    public class Solution {
        public List<List<Integer>> findLeaves(TreeNode root) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            while(root!=null){
                List<Integer> someres=new ArrayList<>();
                helper(root,someres);
                res.add(someres);
            }
            return res;
        }
        public void helper(TreeNode root,List<Integer> curres){
            if(root.left==null&&root.right==null){
                curres.add(root.val);
                root=null;
                return;
            }
            if(root.left!=null)helper(root.left,curres);
            if(root.right!=null) helper(root.right,curres);
        }
    }
    

  • 0
    L

    Sorry, My question was stupid and I understand the reason.


  • 0
    Z

    @lionellijian what's the reason, I have the same problem here. The time exceed limitation, it seems that my leaves aren't removed.


  • 0
    Z

    @lionellijian OK, I understand it too now


  • 4
    T

    I fall into the same pitfall as @lionellijian. For the benefit of people seeing this thread, I want add an explanation here. The root cause is Java function parameter is pass-by-value:

    public void helper(TreeNode root,List<Integer> curres) {
        ....
            root=null; // This line doesn't work
        ...
    }
    

    Therefore, the only way to reset the leave node is through parent:

    if(isLeave(node.left, leaves))  node.left = null;
    

    Great article to explain why Java function parameter is pass-by-value: http://www.javaworld.com/article/2077424/learn-java/does-java-pass-by-reference-or-pass-by-value.html


  • 3
    S

    Similar idea; Recur until you find a leave, add it to the temp list, and return null so root.left / root.right becomes null. Eventually, root will become null.

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

  • 0
    P

    @selim I have almost the same solution as you. Pointer reinforcement is a great way to solve this kind of recursion problem


Log in to reply
 

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