寻找二叉树的叶子节点 图解题解

这道题到底在问什么

输入

root=[1,2,3,4,5]

输出

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

最优解：一步一步想明白

1. 3记住「答案桶下标 = 高度 h = max(左,右)+1，叶子 h=0；屏幕第几轮 = h+1」，下面按轮把叶子逐个剥下来。
2. 4共 11 个节点，待剥 4 轮这是完整的二叉树，共 11 个节点。下面一轮一轮地把当前叶子剥下来；一个节点高度为 h，就落在答案桶 ans[h]，对应屏幕上的第 h+1 轮。
3. 5当前叶子: 20, 60, 35, 75, 70, 90第 1 轮。树最外层、没有孩子的节点（原始叶子）是 20、60、35、75、70、90（紫色）。它们高度都是 0，落在答案桶 ans[0]，对应屏幕第 1 轮。
4. 6收入 20（第 1 轮）把叶子 20 收进第 1 轮（变绿）。它没有还留在树上的孩子，正是当前的叶子。
5. 7收入 60（第 1 轮）把叶子 60 收进第 1 轮（变绿）。它没有还留在树上的孩子，正是当前的叶子。
6. 8收入 35（第 1 轮）把叶子 35 收进第 1 轮（变绿）。它没有还留在树上的孩子，正是当前的叶子。
7. 9收入 75（第 1 轮）把叶子 75 收进第 1 轮（变绿）。它没有还留在树上的孩子，正是当前的叶子。
8. 10收入 70（第 1 轮）把叶子 70 收进第 1 轮（变绿）。它没有还留在树上的孩子，正是当前的叶子。
9. 11收入 90（第 1 轮）把叶子 90 收进第 1 轮（变绿）。它没有还留在树上的孩子，正是当前的叶子。
10. 12第 1 轮完成第 1 轮的叶子 [20,60,35,75,70,90] 全部剥下（转蓝表示已删除）。剩下的节点里，又冒出了新的叶子，进入下一轮。
11. 13当前叶子: 10, 40, 80第 2 轮。前一轮的叶子已剥掉（蓝色），又冒出新的叶子 10、40、80（紫色）。它们高度是 1，落在桶 ans[1]，对应屏幕第 2 轮。
12. 14收入 10（第 2 轮）把叶子 10 收进第 2 轮（变绿）。它没有还留在树上的孩子，正是当前的叶子。
13. 15收入 40（第 2 轮）把叶子 40 收进第 2 轮（变绿）。它没有还留在树上的孩子，正是当前的叶子。
14. 16收入 80（第 2 轮）把叶子 80 收进第 2 轮（变绿）。它没有还留在树上的孩子，正是当前的叶子。
15. 17第 2 轮完成第 2 轮的叶子 [10,40,80] 全部剥下（转蓝表示已删除）。剩下的节点里，又冒出了新的叶子，进入下一轮。
16. 18当前叶子: 30第 3 轮。前一轮的叶子已剥掉（蓝色），又冒出新的叶子 30（紫色）。它们高度是 2，落在桶 ans[2]，对应屏幕第 3 轮。
17. 19收入 30（第 3 轮）把叶子 30 收进第 3 轮（变绿）。它没有还留在树上的孩子，正是当前的叶子。
18. 20第 3 轮完成第 3 轮的叶子 [30] 全部剥下（转蓝表示已删除）。剩下的节点里，又冒出了新的叶子，进入下一轮。
19. 21当前叶子: 50第 4 轮。前一轮的叶子已剥掉（蓝色），又冒出新的叶子 50（紫色）。它们高度是 3，落在桶 ans[3]，对应屏幕第 4 轮。
20. 22收入 50（第 4 轮）把叶子 50 收进第 4 轮（变绿）。它没有还留在树上的孩子，正是当前的叶子。
21. 23树已空第 4 轮的叶子 [50] 全部剥下（转蓝表示已删除）。树已空，结束。
22. 24共 4 轮全部剥完，答案就是每轮收集的列表：[[20,60,35,75,70,90], [10,40,80], [30], [50]]。每个节点恰好落在「桶下标 = 它的高度 h」，对应屏幕第 h+1 轮。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans = []
        def height(node):
            if not node:
                return -1
            h = max(height(node.left), height(node.right)) + 1
            if h == len(ans):
                ans.append([])
            ans[h].append(node.val)
            return h
        height(root)
        return ans

#include <vector>
#include <algorithm>
using namespace std;

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *l, TreeNode *r) : val(x), left(l), right(r) {} };

class Solution {
public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        vector<vector<int>> ans;
        height(root, ans);
        return ans;
    }
private:
    int height(TreeNode* node, vector<vector<int>>& ans) {
        if (!node) return -1;
        int h = max(height(node->left, ans), height(node->right, ans)) + 1;
        if (h == (int)ans.size()) ans.push_back({});
        ans[h].push_back(node->val);
        return h;
    }
};

import java.util.*;

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 {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        height(root, ans);
        return ans;
    }
    private int height(TreeNode node, List<List<Integer>> ans) {
        if (node == null) return -1;
        int h = Math.max(height(node.left, ans), height(node.right, ans)) + 1;
        if (h == ans.size()) ans.add(new ArrayList<>());
        ans.get(h).add(node.val);
        return h;
    }
}

复杂度

面试官可能追问