Tìm giá trị lớn nhất mỗi hàng cây trong C++

Cho cây nhị phân, tìm phần tử lớn nhất ở mỗi cấp độ. Ví dụ cây cho kết quả [3,5,8].

Giải thuật

• Mảng ans lưu kết quả.
• Hàm đệ quy solve(node, level):
  • Nếu node == null trả về.
  • Nếu level == ans.size() thêm node->val vào ans; ngược lại ans[level] = max(ans[level], node->val).
  • Gọi solve(node->left, level+1) và solve(node->right, level+1).
• Gọi solve(root, 0), trả về ans.

Ví dụ mã C++

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

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

class Solution {
public:
    vector<int> ans;
    void solve(TreeNode* node, int level = 0) {
        if (!node) return;
        if (level == ans.size()) ans.push_back(node->val);
        else ans[level] = max(ans[level], node->val);
        solve(node->left, level+1);
        solve(node->right, level+1);
    }
    vector<int> largestValues(TreeNode* root) {
        solve(root);
        return ans;
    }
};

Đầu vào

[1,3,2,5,3,null,9]

Đầu ra

[1, 3, 9, ]