12 lines in Java by calculating height of each node


  • 0
    O

    The idea is to calculate the height of each node. The node in the same height should be put in the same list.

    First look at the simple code for calculating the height. The bottom should be -1 so that the leave node will have the height of 0.

    private int height(TreeNode root) {
        if (root == null) {
            return -1; // touch the bottom
        }
        int left = height(root.left);
        int right = height(root.right);
        return Math.max(left, right) + 1;
    }
    

    Then, we add more code to fullfill this problem.

    public class Solution {
        public List<List<Integer>> findLeaves(TreeNode root) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            dfs(root, res);
            return res;
        }
        
        private int dfs(TreeNode root, List<List<Integer>> res) {
            if (root == null) return -1;
            int left = dfs(root.left, res);
            int right = dfs(root.right, res);
            int height = Math.max(left, right) + 1; // the height of the current node
            if (height >= res.size()) res.add(new ArrayList<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.