home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

ความยาวพาธที่เพิ่มขึ้นต่อเนื่องกันสูงสุดในทรีไบนารีใน C++

สมมติว่าเรามีต้นไม้ไบนารี เราต้องคำนวณความยาวของเส้นทางที่ยาวที่สุดซึ่งประกอบด้วยโหนดที่มีค่าต่อเนื่องกันตามลำดับที่เพิ่มขึ้น ทุกโหนดจะถือว่าเป็นเส้นทางที่มีความยาว 1

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

ความยาวพาธที่เพิ่มขึ้นต่อเนื่องกันสูงสุดในทรีไบนารีใน C++

จากนั้นเอาต์พุตจะเป็น 3 เนื่องจาก (11, 12, 13) เป็นเส้นทางต่อเนื่องสูงสุด

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

  • กำหนดฟังก์ชัน Solve() ซึ่งจะทำการ root, prev_data, prev_length
  • ถ้าไม่ใช่รูทก็ไม่ใช่ศูนย์ ดังนั้น −
    • ส่งคืนprev_length
  • cur_data :=val ของรูท
  • ถ้า cur_data เหมือนกับ prev_data + 1 แล้ว −
    • คืนค่าสูงสุดของการแก้ปัญหา (ด้านซ้ายของ root, cur_data, prev_length+1) และแก้ปัญหา (ด้านขวาของ root, cur_data, prev_length+1)
  • newPathLen :=สูงสุดของการแก้ปัญหา (ด้านซ้ายของ root, cur_data, 1) และการแก้ปัญหา (ด้านขวาของ root, cur_data, 1)
  • คืนค่าสูงสุดของ prev_length และ newPathLen
  • จากวิธีหลัก ให้ทำดังนี้ -
  • ถ้ารูทเหมือนกับ NULL แล้ว −
    • คืน 0
  • ส่งคืนการแก้(root, val ของ root-1, 0)

ตัวอย่าง (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;
      }
};
int solve(TreeNode *root, int prev_data, int prev_length){
   if (!root)
      return prev_length;
   int cur_data = root->val;
   if (cur_data == prev_data+1){
      return max(solve(root->left, cur_data, prev_length+1), solve(root->right, cur_data, prev_length+1));
   }
   int newPathLen = max(solve(root->left, cur_data, 1), solve(root->right, cur_data, 1));
   return max(prev_length, newPathLen);
}
int maxLen(TreeNode *root){
   if (root == NULL)
      return 0;
   return solve(root, root->val-1, 0);
}
int main(){
   TreeNode *root = new TreeNode(10);
   root->left = new TreeNode(11);
   root->right = new TreeNode(9);
   root->left->left = new TreeNode(13);
   root->left->right = new TreeNode(12);
   root->right->left = new TreeNode(13);
   root->right->right = new TreeNode(8);
   cout << maxLen(root);
   return 0;
}

อินพุต

TreeNode *root = new TreeNode(10);
root->left = new TreeNode(11);
root->right = new TreeNode(9);
root->left->left = new TreeNode(13);
root->left->right = new TreeNode(12);
root->right->left = new TreeNode(13);
root->right->right = new TreeNode(8);

ผลลัพธ์

3