Góc nhìn bên phải cây nhị phân trong C++

Giả sử chúng ta có một cây nhị phân, nếu nhìn cây từ bên phải, chúng ta có thể thấy một số phần tử của nó. Chúng ta phải hiển thị các phần tử đó. Vì vậy, nếu cây như sau:

Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:

• Chúng ta sẽ tạo một phương thức hỗ trợ cho dfs. Phương thức này nhận node cây, một mảng chứa câu trả lời, và cấp độ. Cấp độ ban đầu là 0. dfs sẽ hoạt động như sau:
• nếu node là null, trả về
• nếu cấp độ = độ dài mảng câu trả lời, thì chèn giá trị node vào mảng ans
• dfs(phải của node, ans, cấp độ + 1)
• dfs(trái của node, ans, cấp độ + 1)
• Từ hàm chính gọi dfs() sử dụng gốc của cây và một mảng rỗng, cấp độ ban đầu là 0, nên sẽ là dfs(root, ans)

Hãy xem triển khai sau để hiểu rõ hơn:

Ví dụ

#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;
    }
};
void insert(TreeNode **root, int val){
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()){
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left){
            if(val != NULL)
                temp->left = new TreeNode(val);
            else
                temp->left = new TreeNode(0);
            return;
        } else {
            q.push(temp->left);
        }
        if(!temp->right){
            if(val != NULL)
                temp->right = new TreeNode(val);
            else
                temp->right = new TreeNode(0);
            return;
        } else {
            q.push(temp->right);
        }
    }
}
TreeNode *make_tree(vector<int> v){
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        insert(&root, v[i]);
    }
    return root;
}
class Solution {
public:
    void dfs(TreeNode* node, vector <int>& ans, int level = 0){
        if(!node) return;
        if(level == ans.size())ans.push_back(node->val);
        dfs(node->right, ans, level + 1);
        dfs(node->left, ans, level + 1);
    }
    vector<int> rightSideView(TreeNode* root) {
        vector <int> ans;
        dfs(root, ans);
        return ans;
    }
};
main(){
    vector<int> v = {1,2,3,NULL,5,NULL,4};
    TreeNode *root = make_tree(v);
    Solution ob;
    print_vector(ob.rightSideView(root));
}

Đầu vào

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

Đầu ra

[1, 3, 4, ]