10 lines simple Java solution using recursion with explanation


  • 124
    public class Solution {
        public List<List<Integer>> findLeaves(TreeNode root) {
            List<List<Integer>> res = new ArrayList<>();
            height(root, res);
            return res;
        }
        private int height(TreeNode node, List<List<Integer>> res){
            if(null==node)  return -1;
            int level = 1 + Math.max(height(node.left, res), height(node.right, res));
            if(res.size()<level+1)  res.add(new ArrayList<>());
            res.get(level).add(node.val);
            return level;
        }
    }
    

    For this question we need to take bottom-up approach. The key is to find the height of each node. Here the definition of height is:
    The height of a node is the number of edges from the node to the deepest leaf. --CMU 15-121 Binary Trees

    I used a helper function to return the height of current node. According to the definition, the height of leaf is 0. h(node) = 1 + max(h(node.left), h(node.right)).
    The height of a node is also the its index in the result list (res). For example, leaves, whose heights are 0, are stored in res[0]. Once we find the height of a node, we can put it directly into the result.

    UPDATE:
    Thanks @adrianliu0729 for pointing out that my previous code does not actually remove leaves. I added one line node.left = node.right = null; to remove visited nodes

    UPDATE:
    There seems to be some debate over whether we need to actually "remove" leaves from the input tree. Anyway, it is just a matter of one line code. In the actual interview, just confirm with the interviewer whether removal is required.


  • 0
    A

    Wow, that's simple and elegant. Good job.


  • 14

    Nice. Got almost exactly the same, but in Python. Only real difference is that my extension criterion is like level == res.size(), checking equality. I think the < makes it look like res.size() could actually be smaller than level, and I don't like giving that impression.

    def findLeaves(self, root):
        def dfs(node):
            if not node:
                return -1
            i = 1 + max(dfs(node.left), dfs(node.right))
            if i == len(out):
                out.append([])
            out[i].append(node.val)
            return i
        out = []
        dfs(root)
        return out

  • 1
    D

    Great solution. Took me some time to understand the logic behind this. So the helper function returns the level of current "node" counting from its furtherest leaf child, right? For ex, the leaf node will have a level of 0, and its parent will have level of 1, and so on. Correct if I'm interpreting it wrong, please. Thanks.


  • 0

    Yes you are right. The helper function return the height of current node. Leaf will have a height of 0.


  • 4
    S

    @sky-xu Beautiful! It clearly shows the thought/understanding of how recursion/dfs flows out. I wish I could upvote more than once of your answer. And I'm really impressed by how you nicely took advantage of using level as the index of the result. Thumbs-up!


  • 0
    A

    The question asks us to remove the leaf nodes every time we find it, I don't think your code did this, but apparently OJ is not checking this so your soln passed without any issue.


  • 0
    Q

    Nice solution! However, the root doesn't exist in helper function. It should be node I think~


  • 0

    @qiong7 You are right. Thanks for pointing out!


  • 0
    A

    This problem does not actually ask you to remove leaves. It says collect nodes as if you are removing leaves. It's also bad to modify input data structure.


  • 0
    Y

    said in 10 lines simple Java solution using recursion with explanation:

    res

    you idea is exact the same as me by utilizing the height of each nodes, but with recursion, it looks more concise.


  • 0

    @Adeath said in 10 lines simple Java solution using recursion with explanation:

    This problem does not actually ask you to remove leaves.

    Originally, it did.


  • 0

    @StefanPochmann I like this style more, too. BTW, does it belong to backtracking algorithm?


  • 0
    M

    Wow!! This solution is really elegant.


  • 0

    Nice solution, thanks for sharing!!

    I am still wondering, do you need to remove nodes from the tree? The problem description is not very clear about that. You get the exact answer with the tree unchanged.


  • 0
    Z

    @zhugejunwei
    Actually I would like to call it post order traversal.


  • 0
    R

    Thank you! Your explanation is very clear.


  • 0
    L

    Wooow. Good solution 😘😘😘😘😘


  • -1
    C
    
        public List<List<Integer>> findLeaves(TreeNode root) {
            List<List<Integer>> res = new ArrayList<>();
            helper(root , res);
            return res;
        }
        int helper(TreeNode root , List<List<Integer>> res){
            if(root == null) return -1;
            
            int height = 1 + Math.max(helper(root.left , res) , helper(root.right , res));
            if(height == res.size()){
                res.add(new ArrayList<>());
            }
            res.get(height).add(root.val);
            return height;
        }
    
    

  • 0
    Z

    Nice solution! It's all about counting the height. No need to hashing.

        public List<List<Integer>> findLeaves(TreeNode root) {
            List<List<Integer>> res =  new ArrayList<>();
            T(res,root);
            return res;
        }
        private int T(List<List<Integer>>res, TreeNode root){
                if(root==null)return -1;
                int height = Math.max(T(res,root.left),T(res,root.right))+1;
                if(height==res.size()){res.add(new LinkedList<Integer>());}
                res.get(height).add(root.val);
                return height;
            }
    

Log in to reply
 

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