Tìm giá trị cây dưới cùng bên trái trong C ++

Giả sử chúng ta có một cây nhị phân. Chúng ta phải tìm giá trị cao nhất bên trái của hàng cuối cùng của cây đó. Vì vậy, nếu cây như -

Sau đó, đầu ra sẽ là 7, vì hàng cuối cùng là [7, 4] và phần tử bên trái hầu hết là 7.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ban đầu xác định biến ans và lvl là 0

• xác định một phương thức có tên là giải quyết (), phương thức này sẽ lấy nút cây và mức, mức ban đầu là 0. Điều này sẽ hoạt động như sau -

• nếu nút là null, thì trả về

• nếu cấp> lvl, thì ans:=giá trị của nút và lvl:=cấp

• giải quyết (bên trái của nút, mức + 1)

• giải quyết (bên phải của nút, mức + 1)

• Trong phần chính, đặt lvl:=-1, gọi giải quyết (root) và trả về ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> 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 = NULL;
      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:
   int ans;
   int lvl;
   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;
   }
};
main(){
   vector<int> v = {3,5,1,6,2,0,8,NULL,NULL,7,4};
   TreeNode *tree = make_tree(v);
   Solution ob;
   cout <<(ob.findBottomLeftValue(tree));
}

Đầu vào

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

Đầu ra

7