Binary Tree ต่อเนื่องกันที่ยาวที่สุดใน C++

สมมติว่าเรามีต้นไม้ไบนารี เราต้องตรวจสอบว่าเราสามารถหาความยาวของเส้นทางลำดับต่อเนื่องที่ยาวที่สุดได้หรือไม่ หากพาธอ้างอิงถึงลำดับของโหนดใดๆ จากโหนดเริ่มต้นบางโหนดไปยังโหนดใดๆ ในแผนผังตามการเชื่อมต่อหลัก-ชายด์ เส้นทางที่ยาวที่สุดต่อเนื่องกันต้องเดินตามพ่อแม่ไปสู่ลูก แต่อย่าย้อนกลับ

ดังนั้นหากอินพุตเป็นแบบนั้น

จากนั้นผลลัพธ์จะเป็น 3 เนื่องจากเส้นทางลำดับที่ยาวที่สุดต่อเนื่องกันคือ 3-4-5 ดังนั้นให้คืนค่า 3

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

• กำหนดฟังก์ชัน SolvUtil() ซึ่งจะใช้โหนด ก่อนหน้า len เริ่มต้นด้วย 1

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

  • กลับ

• ถ้าก่อนหน้า + 1 เหมือนกับ val ของโหนด ดังนั้น −

  • (เพิ่มเลน 1)

  • ans :=สูงสุดของ ans และ len

  • SolvUtil(ซ้ายของโหนด, val ของโหนด, len)

  • SolvUtil(ด้านขวาของโหนด, ค่าของโหนด, len)

• มิฉะนั้น

  • SolvUtil(ด้านซ้ายของโหนด, val ของโหนด, 1)

  • SolvUtil(ด้านขวาของโหนด ค่าของโหนด 1)

• กำหนดฟังก์ชัน Solve() ซึ่งจะใช้ A

• ตอบ :=1

• SolvUtil(A, -อินฟินิตี้)

• กลับมาอีกครั้ง

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• ถ้ารูทเป็นโมฆะ −

  • คืนค่า 0

• คืนค่าแก้(รูท)

ตัวอย่าง

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

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

อินพุต

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);

ผลลัพธ์

3