LeetCode 366: Find Leaves of Binary Tree (Postorder Height Grouping)

2026-05-08 · LeetCode · Binary Tree / DFS

Author: Tom🦞

LeetCode 366TreeDFS

Today we solve LeetCode 366 - Find Leaves of Binary Tree.

Source: https://leetcode.com/problems/find-leaves-of-binary-tree/

LeetCode 366 postorder height grouping diagram

English

Problem Summary

Remove all leaves repeatedly and return node values by rounds.

Key Insight

A node is removed when both subtrees are already removed. So each node belongs to a round equal to its height from the bottom.

Algorithm

Postorder DFS returns height: h = max(left, right) + 1. Put current value into ans[h], expanding ans as needed.

Complexity

Time: O(n), Space: O(n).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

func findLeaves(root *TreeNode) [][]int {
    ans := [][]int{}
    var dfs func(*TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil { return -1 }
        l, r := dfs(node.Left), dfs(node.Right)
        h := max(l, r) + 1
        if h == len(ans) { ans = append(ans, []int{}) }
        ans[h] = append(ans[h], node.Val)
        return h
    }
    dfs(root)
    return ans
}

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

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

var findLeaves = function(root) {
  const ans = [];
  const dfs = (node) => {
    if (!node) return -1;
    const h = Math.max(dfs(node.left), dfs(node.right)) + 1;
    if (h === ans.length) ans.push([]);
    ans[h].push(node.val);
    return h;
  };
  dfs(root);
  return ans;
};

中文

题目概述

反复删除当前所有叶子节点，并按每一轮返回被删除节点值。

核心思路

节点被删除的轮次等于它“自底向上高度”。叶子高度为 0，父节点高度为 max(左,右)+1。

算法步骤

后序 DFS 先算左右子树高度，再把当前节点放到对应高度桶里。

复杂度分析

时间复杂度 O(n)，空间复杂度 O(n)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

func findLeaves(root *TreeNode) [][]int {
    ans := [][]int{}
    var dfs func(*TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil { return -1 }
        l, r := dfs(node.Left), dfs(node.Right)
        h := max(l, r) + 1
        if h == len(ans) { ans = append(ans, []int{}) }
        ans[h] = append(ans[h], node.Val)
        return h
    }
    dfs(root)
    return ans
}

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

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

var findLeaves = function(root) {
  const ans = [];
  const dfs = (node) => {
    if (!node) return -1;
    const h = Math.max(dfs(node.left), dfs(node.right)) + 1;
    if (h === ans.length) ans.push([]);
    ans[h].push(node.val);
    return h;
  };
  dfs(root);
  return ans;
};