Binary Tree ลำดับที่ยาวที่สุดติดต่อกัน II ใน C++

สมมติว่าเรามีต้นไม้ไบนารี เราต้องหาความยาวของเส้นทางติดต่อกันที่ยาวที่สุดในต้นไม้ไบนารีนั้น ที่นี่เส้นทางสามารถเพิ่มขึ้นหรือลดลงได้ ตัวอย่างเช่น [1,2,3,4] และ [4,3,2,1] ถือเป็นเส้นทางที่ถูกต้อง แต่เส้นทาง [1,2,4,3] ไม่ใช่เส้นทางที่ถูกต้อง

มิฉะนั้น เส้นทางสามารถอยู่ในลำดับ child-Parent-child โดยไม่จำเป็นต้องเป็นลำดับ parent-child

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

จากนั้นผลลัพธ์จะเป็น 3 เนื่องจากเส้นทางที่ยาวที่สุดติดต่อกันจะเป็นเช่น [1, 2, 3] หรือ [3, 2, 1]

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

• กำหนดฟังก์ชัน SolvUtil() ซึ่งจะรับโหนด

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

  • กลับ { 0, 0 }

• ซ้าย =SolvUtil (ด้านซ้ายของโหนด)

• ซ้าย =SolvUtil (ทางขวาของโหนด)

• กำหนดหนึ่งคู่ temp :={1,1}

• หากมีโหนดด้านซ้ายและค่าของโหนดด้านซ้ายเท่ากับค่าของโหนด + 1 ดังนั้น −

  • temp.first :=สูงสุดของ temp.first และ 1 + left.first

  • ans :=สูงสุดของ ans และ temp.first

• หากสิทธิ์ของโหนดมีอยู่และมูลค่าของโหนดเท่ากับค่าของโหนด + 1 ดังนั้น −

  • temp.first :=สูงสุดของ temp.first และ 1 + right.first

  • ans :=สูงสุดของ ans และ temp.first

• หากมีโหนดด้านซ้ายและค่าของโหนดด้านซ้ายเท่ากับค่าของโหนด - 1 ดังนั้น −

  • temp.second :=สูงสุดของ temp.second และ 1 + left.second

  • ans :=สูงสุดของ ans และ temp.second

• หากสิทธิ์ของโหนดมีอยู่และมูลค่าของโหนดเท่ากับค่าของโหนด - 1 ดังนั้น −

  • temp.second :=สูงสุดของ temp.second และ 1 + right.second

  • ans :=สูงสุดของ ans และ temp.second

• ans :=สูงสุด { ans และ temp.first + temp.second - 1 }

• อุณหภูมิกลับ

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

• ตอบ :=0

• SolvUtil(รูท)

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

ตัวอย่าง

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

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
class Solution {
public:
   int ans = 0;
   pair<int, int> solveUtil(TreeNode* node){
      if (!node) {
         return { 0, 0 };
      }
      pair<int, int> left = solveUtil(node->left);
      pair<int, int> right = solveUtil(node->right);
      pair<int, int> temp = { 1, 1 };
      if (node->left && node->left->val == node->val + 1) {
         temp.first = max(temp.first, 1 + left.first);
         ans = max(ans, temp.first);
      }
      if (node->right && node->right->val == node->val + 1) {
         temp.first = max(temp.first, 1 + right.first);
         ans = max(ans, temp.first);
      }
      if (node->left && node->left->val == node->val - 1) {
         temp.second = max(temp.second, 1 + left.second);
         ans = max(ans, temp.second);
      }
      if (node->right && node->right->val == node->val - 1) {
         temp.second = max(temp.second, 1 + right.second);
         ans = max(ans, temp.second);
      }
      ans = max({ ans, temp.first + temp.second - 1 });
      return temp;
   }
   int longestConsecutive(TreeNode* root){
      ans = 0;
      solveUtil(root);
      return ans;
   }
};
main(){
   Solution ob;
   TreeNode *root = new TreeNode(2);
   root->left = new TreeNode(1);
   root->right = new TreeNode(3);
   cout << (ob.longestConsecutive(root));
}

อินพุต

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

ผลลัพธ์

3