Tìm giá trị trái dưới cùng của cây trong C++

Cho cây nhị phân, tìm giá trị trái nhất của hàng cuối cùng. Ví dụ: cây có hàng cuối [7,4] → giá trị trái nhất là 7.

Giải thuật

• ans := 0, lvl := 0.
• Hàm đệ quy solve(node, level):
  • Nếu node == null hoặc node->val == 0 trả về.
  • Nếu level > lvl: ans = node->val, lvl = level.
  • Gọi solve(node->left, level+1), solve(node->right, level+1).
• Trong hàm chính: lvl := -1, gọi solve(root), trả về ans.

Ví dụ mã 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, lvl = -1;
    void solve(TreeNode* node, int level = 0) {
        if (!node || node->val == 0) return;
        if (level > lvl) { ans = node->val; lvl = level; }
        solve(node->left, level+1);
        solve(node->right, level+1);
    }
    int findBottomLeftValue(TreeNode* root) {
        lvl = -1;
        solve(root);
        return ans;
    }
};

Đầu vào

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

Đầu ra

7