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

สมมติว่าเรามีต้นไม้ไบนารี ถ้าเราเห็นต้นไม้จากด้านซ้าย เราก็จะเห็นองค์ประกอบบางอย่างของมัน เราต้องแสดงองค์ประกอบเหล่านั้น ดังนั้นถ้าต้นไม้เป็นเหมือน −

ผลลัพธ์จะเป็น [1,2,5]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดอาร์เรย์ ret

• กำหนดฟังก์ชัน dfs() สิ่งนี้จะใช้โหนด c เริ่มต้นด้วย 1

• ถ้าโหนดเป็นโมฆะ −

  • กลับ

• ถ้า c> เลเวล แล้ว −

  • เลเวล :=ค

  • แทรกค่าของโหนดใน ret

• dfs(ด้านซ้ายของโหนด c + 1)

• dfs(ทางขวาของโหนด c + 1)

• จากวิธีหลัก ให้ทำดังนี้ −

• เลเวล :=-1

• dfs(root, 0)

• รีเทิร์น

  
  

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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