หาค่าด้านซ้ายสุดของแถวสุดท้ายในต้นไม้แบนารี (Find Bottom Left Tree Value) ใน C++

หาค่าด้านซ้ายสุดของแถวสุดท้าย (Find Bottom Left Tree Value)

ให้ต้นไม้แบนารี หาค่าของโหนดที่อยู่ด้านซ้ายสุดในระดับลึกที่สุด (deepest level)

ตัวอย่าง: ต้นไม้ [3,5,1,6,2,0,8,null,null,7,4] → ระดับสุดท้ายคือ [7,4] ค่าซ้ายสุดคือ 7

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

1. กำหนดตัวแปร ans และ maxLevel = -1
2. ฟังก์ชัน solve(node, level):
   • ถ้า node == null คืนค่า
   • ถ้า level > maxLevel: ans = node.val, maxLevel = level
   • เรียก 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:
    int ans = 0, maxLevel = -1;
    void solve(TreeNode* node, int level = 0) {
        if (!node) return;
        if (level > maxLevel) {
            ans = node->val;
            maxLevel = level;
        }
        solve(node->left, level + 1);
        solve(node->right, level + 1);
    }
    int findBottomLeftValue(TreeNode* root) {
        maxLevel = -1;
        solve(root);
        return ans;
    }
};

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

Input: [3,5,1,6,2,0,8,null,null,7,4]

Output: 7