หาค่าสูงสุดแต่ละระดับของต้นไม้แบนารี (Largest Value in Each Tree Row) ใน C++

หาค่าสูงสุดแต่ละระดับของต้นไม้แบนารี (Find Largest Value in Each Tree Row)

ให้ต้นไม้แบนารี หาค่าสูงสุดในแต่ละระดับ (level) ของต้นไม้

ตัวอย่าง: ต้นไม้ [1,3,2,5,3,null,9] → ผลลัพธ์ [3,5,9] (ระดับ 0: 1, ระดับ 1: max(3,2)=3, ระดับ 2: max(5,3,9)=9)

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

1. สร้างเวกเตอร์ ans เก็บค่าสูงสุดแต่ละระดับ
2. กำหนดฟังก์ชัน solve(node, level):
   • ถ้า node == null คืนค่า
   • ถ้า level == ans.size() เพิ่ม node.val เข้า ans
   • มิฉะนั้น ans[level] = max(ans[level], node.val)
   • เรียก solve(node.left, level+1) และ solve(node.right, level+1)
3. เรียก solve(root, 0) แล้วคืนค่า ans

ตัวอย่างโค้ด 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;
    }
};

อินพุทและเอาต์พุทตัวอย่าง

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

Output: [3,5,9]