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

Giả sử chúng ta có một cây nhị phân; chúng ta phải tìm độ dài của Đường đi liên tiếp dài nhất trong Cây nhị phân đó. Ở đây đường dẫn có thể tăng hoặc giảm. Vì vậy, như một ví dụ [1,2,3,4] và [4,3,2,1] đều được coi là một đường dẫn hợp lệ, nhưng đường dẫn [1,2,4,3] không phải là một đường dẫn hợp lệ.

Nếu không, đường dẫn có thể theo trình tự con-Cha-con, trong đó không nhất thiết phải là thứ tự cha-con.

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

thì đầu ra sẽ là 3 vì đường dẫn liên tiếp dài nhất sẽ giống như [1, 2, 3] hoặc [3, 2, 1].

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

• Xác định một hàm giải quyếtUtil (), hàm này sẽ sử dụng nút,

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

  • trả lại {0, 0}

• left =giải quyếtUtil (bên trái của nút)

• left =giải quyếtUtil (bên phải của nút)

• Xác định tạm thời một cặp:={1,1}

• nếu bên trái của nút có mặt và giá trị bên trái của nút giống với giá trị của nút + 1, thì -

  • temp.first:=tối đa của temp.first và 1 + left.first

  • ans:=tối đa ans và temp.first

• nếu bên phải của nút có mặt và giá trị của bên phải của nút giống với giá trị của nút + 1, thì -

  • temp.first:=tối đa của temp.first và 1 + right.first

  • ans:=tối đa ans và temp.first

• nếu bên trái của nút có mặt và giá trị bên trái của nút giống với giá trị của nút - 1, thì -

  • temp.second:=tối đa temp.second và 1 + left.second

  • ans:=tối đa ans và temp.second

• nếu bên phải của nút có mặt và giá trị của bên phải của nút giống với giá trị của nút - 1, thì -

  • temp.second:=tối đa của temp.second và 1 + right.second

  • ans:=tối đa ans và temp.second

• ans:=tối đa là {ans và temp.first + temp.second - 1}

• trở lại nhiệt độ

• Từ phương thức chính, hãy làm như sau -

• ans:=0

• giải quyết (root)

• trả lại ans

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

Đầu vào

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

Đầu ra

3