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

Độ dài đường dẫn tăng liên tiếp tối đa trong 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 tính độ dài của con đường dài nhất bao gồm các nút có giá trị liên tiếp theo thứ tự tăng dần. Mọi nút sẽ được coi là một đường dẫn có độ dài 1.

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

Độ dài đường dẫn tăng liên tiếp tối đa trong cây nhị phân trong C ++

thì đầu ra sẽ là 3 vì (11, 12, 13) là đường dẫn liên tiếp tối đa.

Để 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ết (), hàm này sẽ có giá trị gốc, dữ liệu trước đó, giá trị phổ biến nhất,
  • nếu không gốc là khác 0, thì -
    • trả về trước_lực lượng
  • cur_data:=val of root
  • nếu cur_data giống như pres_data + 1, thì -
    • trả về tối đa giải quyết (bên trái của thư mục gốc, cur_data, prev_length + 1) và giải quyết (bên phải thư mục gốc, cur_data, pres_length + 1)
  • newPathLen:=tối đa giải quyết (bên trái của root, cur_data, 1) và giải quyết (bên phải của root, cur_data, 1)
  • trả về giá trị tối đa của pres_length và newPathLen
  • Từ phương thức chính, hãy làm như sau -
  • nếu gốc giống như NULL, thì -
    • trả về 0
  • trả về giải quyết (root, val của root-1, 0)

Ví dụ (C ++)

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

Đầu vào 

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

Đầu ra 

3