Chương trình tìm giao diện bên trái của cây nhị phân trong C++

Cho một cây nhị phân. Nếu nhìn từ bên trái, ta sẽ thấy một số nút. Hãy xuất các nút đó (Left Side View).

Ví dụ: cây gốc 1, trái 2, phải 3, 2->phải 5, 3->phải 4 → kết quả: [1, 2, 5].

Thuật toán (DFS ưu tiên trái)

• Dùng DFS, tham số c là độ sâu hiện tại (bắt đầu từ 1).
• Biến lvl lưu độ sâu lớn nhất đã thăm.
• Khi thăm nút: nếu c > lvl, cập nhật lvl = c và thêm giá trị nút vào kết quả.
• Đệ quy trái trước, sau đó phải.

Ví dụ triển khai (C++)

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

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

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

class Solution {
public:
    vector<int> ret;
    int lvl;
    void dfs(TreeNode* node, int c = 1) {
        if (!node) return;
        if (c > lvl) { lvl = c; ret.push_back(node->val); }
        dfs(node->left, c + 1);
        dfs(node->right, c + 1);
    }
    vector<int> solve(TreeNode* root) {
        lvl = -1;
        dfs(root, 0);
        return ret;
    }
};

int main() {
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(4);
    Solution ob;
    print_vector(ob.solve(root));
    return 0;
}

Đầu vào

TreeNode *root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->right = new TreeNode(5); root->right->right = new TreeNode(4);

Đầu ra

[1,2,5]