> For the complete documentation index, see [llms.txt](https://soloveri.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soloveri.gitbook.io/leetcode/tree/366-find-leaves-of-binary-tree.md).

# 366-Find-Leaves-of-Binary-Tree

[原题链接](https://leetcode-cn.com/problems/find-leaves-of-binary-tree/)

## 0x0 题目详情

> 给你一棵二叉树，请按以下要求的顺序收集它的全部节点： 依次从左到右，每次收集并删除所有的叶子节点 重复如上过程直到整棵树为空

**测试用例:**

> 示例: 输入: \[1,2,3,4,5]

```
         1
        / \
       2   3
      / \     
     4   5    
```

> 输出: \[\[4,5,3],\[2],\[1]] 解释:

1.删除叶子节点 \[4,5,3] ，得到如下树结构：

```
  1
 / 
2          
```

2.现在删去叶子节点 \[2] ，得到如下树结构：

```
1          
```

3.现在删去叶子节点 \[1] ，得到空树：

```
[]         
```

## 0x1 解题思路

这道题的难点在于当我们遇到叶子节点时,我们需要知道它应该放到哪个集合中。所以当递归到叶子节点往上回溯时,我们附带向上层传递本层节点的层数。当前节点的层数取左右节点传回的较大的值。

然后因为结果集的存放是有规律的:第一层放到第一个集合,第二层放到第二个集合,...,以此类推,就将层数信息和对应的集合联系了起来(这里的层数由下往上,最底层为第一层)。

编写递归代码就比较简单了。

## 0x2 实现代码

遍历了n个节点,时间复杂度为O(N)。

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> result;
    public List<List<Integer>> findLeaves(TreeNode root) {
        result=new ArrayList<>();
        if(root==null){
            return result;
        }
        recur(root);
        return result;

    }
    private int recur(TreeNode root){
        if(root==null){
            return 0;
        }
        //返回左子树的高度
        int left=recur(root.left);
        //返回右子树的高度
        int right=recur(root.right);
        int current=Math.max(left,right)+1;
        //如果是新集合,那么就new一个
        if(current>result.size()){
            result.add(new ArrayList<Integer>());
            result.get(result.size()-1).add(root.val);
        }else{
            //否则通过层数找到对应的集合加入 当前节点
            result.get(current-1).add(root.val);
        }
        return current;
    }
}
```

## 0x3 课后总结

老生常谈！！！树的题目:

* 要么从根节点开始递归由上至下收集答案,直至遇到根节点
* 要么先递归到子节点,然后由下到上收集答案


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://soloveri.gitbook.io/leetcode/tree/366-find-leaves-of-binary-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.