โปรแกรมหามุมมองด้านซ้ายของต้นไม้ไบนารีใน C++

สมมติว่าเรามีต้นไม้ไบนารี หากมองจากด้านซ้าย เราจะเห็นโหนดบางส่วน เราต้องแสดงโหนดเหล่านั้นออกมา

เช่น ต้นไม้ที่มีโครงสร้างดังภาพ ผลลัพธ์จะเป็น [1, 2, 5]

ขั้นตอนการแก้ปัญหา

• สร้างอาร์เรย์ ret เก็บผลลัพธ์
• สร้างฟังก์ชัน dfs(node, level) โดย level เริ่มจาก 1:
  • ถ้า node เป็น null: return
  • ถ้า level > lvl (ระดับสูงสุดที่เจอ): อัปเดต lvl = level, ใส่ค่า node เข้า ret
  • เรียก dfs(node->left, level + 1)
  • เรียก dfs(node->right, level + 1)
• จาก main: ตั้ง lvl = -1, เรียก dfs(root, 0), คืนค่า ret

ตัวอย่างโค้ด

#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));
}

อินพุต

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);

เอาต์พุต

[1,2,5]