Computer >> Máy Tính >  >> Lập trình >> C ++

Chuỗi liên tiếp dài nhất cây nhị phân trong C ++

Giả sử chúng ta có một cây nhị phân; chúng ta phải kiểm tra xem chúng ta có thể tìm thấy độ dài của đường dẫn dãy liên tiếp dài nhất hay không. Nếu đường dẫn tham chiếu đến bất kỳ chuỗi nút nào từ một số nút bắt đầu đến bất kỳ nút nào trong cây dọc theo các kết nối cha-con. Đường dẫn liên tiếp dài nhất cần phải theo từ mẹ đến con nhưng không được đảo ngược.

Vì vậy, nếu đầu vào giống như,

Chuỗi liên tiếp dài nhất cây nhị phân trong C ++

thì đầu ra sẽ là 3, vì đường dẫn trình tự dài nhất liên tiếp là 3-4-5, vì vậy trả về 3.

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

  • Định nghĩa một hàm giải quyết Util (), hàm này sẽ lấy nút, trước, len khởi tạo nó bằng 1,

  • nếu nút là null, thì -

    • trở lại

  • nếu trước + 1 giống với val của nút, thì -

    • (tăng len lên 1)

    • ans:=tối đa ans và len

    • giải quyếtUtil (bên trái của nút, val của nút, len)

    • giải quyết (bên phải của nút, val của nút, len)

  • Nếu không

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

    • giải quyếtUtil (bên phải của nút, val của nút, 1)

  • Xác định một hàm giải quyết (), điều này sẽ nhận A,

  • ans:=1

  • giải quyết vấn đề (A, -infinity)

  • trả lại ans

  • Từ phương thức chính, thực hiện như sau -

  • nếu gốc là null, thì -

    • trả về 0

  • trả về giải quyết (root)

Ví dụ

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

#include <bits/stdc++.h>
using namespace std;
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;
   void solveUtil(TreeNode* node, int prev, int len = 1){
      if (!node)
         return;
      if (prev + 1 == node->val) {
         len++;
         ans = max(ans, len);
         solveUtil(node->left, node->val, len);
         solveUtil(node->right, node->val, len);
      }
      else {
         solveUtil(node->left, node->val, 1);
         solveUtil(node->right, node->val, 1);
      }
   }
   int solve(TreeNode* A){
      ans = 1;
      solveUtil(A, INT_MIN);
      return ans;
   }
   int longestConsecutive(TreeNode* root){
      if (!root)
         return 0;
      return solve(root);
   }
};
main(){
   Solution ob;
   TreeNode *root = new TreeNode(1);
   root->right = new TreeNode(3);
   root->right->left = new TreeNode(2);
   root->right->right = new TreeNode(4);
   root->right->right->right = new TreeNode(5);
   cout << (ob.longestConsecutive(root));
}

Đầu vào 

TreeNode *root = new TreeNode(1);
root->right = new TreeNode(3);
root->right->left = new TreeNode(2);
root->right->right = new TreeNode(4);
root->right->right->right = new TreeNode(5);

Đầu ra 

3