366. Find Leaves of Binary Tree

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given a binary tree, collect a tree’s nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Example:

Input: [1,2,3,4,5]

          1
         / \
        2   3
       / \
      4   5

Output: [[4,5,3],[2],[1]]

Explanation:

1. Removing the leaves [4,5,3] would result in this tree:

          1
         /
        2

1. Now removing the leaf [2] would result in this tree:

          1

1. Now removing the leaf [1] would result in the empty tree:

              []

[[3,5,4],[2],[1]], [[3,4,5],[2],[1]], etc, are also consider correct answers since per each level it doesn’t matter the order on which elements are returned.

Code

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;
        // 先序遍历
        // 相当于把当前节点设置为null
        if (root.left == null && root.right == null) {
            temp.add(root.val);
            return null;
        }
        // 给root赋了新值
        root.left = removeLeaves(root.left, temp);
        root.right = removeLeaves(root.right, temp);
        // 返回了新的root
        return root;
    }
}