C++의 이진 트리에서 최대 연속 증가 경로 길이

<시간/>

이진 트리가 있다고 가정합니다. 오름차순으로 연속적인 값을 갖는 노드로 구성된 가장 긴 경로의 길이를 계산해야 합니다. 모든 노드는 길이가 1인 경로로 처리됩니다.

따라서 입력이 다음과 같으면

(11, 12, 13)이 최대 연속 경로이므로 출력은 3이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

solve() 함수를 정의하면 루트, prev_data, prev_length,
루트가 0이 아닌 경우 -
- prev_length 반환
cur_data :=루트 값
cur_data가 prev_data + 1과 같으면 -
- solve(root의 왼쪽, cur_data, prev_length+1) 및 solve(root의 오른쪽, cur_data, prev_length+1)의 최대값을 반환
newPathLen :=solve(루트의 왼쪽, cur_data, 1) 및 solve(루트의 오른쪽, cur_data, 1)의 최대값
prev_length 및 newPathLen의 최대값 반환
메인 방법에서 다음을 수행하십시오 -
루트가 NULL과 같으면 -
- 0을 반환
return solve(root, val of 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);