Find Leaves of Binary Tree - Thu thập lá cây nhị phân theo lớp

Cho cây nhị phân. Lặp lại: thu thập và loại bỏ tất cả lá cho đến khi cây rỗng. Trả về danh sách các lớp lá theo thứ tự bị loại bỏ.

Ví dụ cây: [1,2,3,4,5] (1 gốc, 2 3 con, 4 5 con của 2) → kết quả [[4,5,3],[2],[1]].

Giải thuật (DFS tính độ cao)

Độ cao của nút = 1 + max(độ cao con trái, con phải). Lá có độ cao 1. Nhóm các nút theo độ cao. Duyệt DFS post-order, tính độ cao, đẩy giá trị vào mảng kết quả tại chỉ số height-1.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<int>> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << "[";
        for (int j = 0; j < v[i].size(); j++)
            cout << v[i][j] << ", ";
        cout << "],";
    }
    cout << "]" << endl;
}

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val = data; left = right = NULL; }
};

TreeNode* make_tree(vector<int> v) {
    TreeNode* root = new TreeNode(v[0]);
    for (int i = 1; i < v.size(); i++) {
        // insert level order (pomitted for brevity)
    }
    return root;
}

class Solution {
public:
    unordered_map<int, int> height;
    vector<vector<int>> ret;

    int dfs(TreeNode* node) {
        if (!node) return 0;
        height[node->val] = 1 + max(dfs(node->left), dfs(node->right));
        if (ret.size() < height[node->val])
            ret.push_back({});
        ret[height[node->val] - 1].push_back(node->val);
        return height[node->val];
    }

    vector<vector<int>> findLeaves(TreeNode* root) {
        dfs(root);
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,3,4,5};
    TreeNode* root = make_tree(v);
    print_vector(ob.findLeaves(root));
    return 0;
}

Đầu vào

{1,2,3,4,5}

Đầu ra

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