C++에서 이진 트리 가장 긴 연속 시퀀스 II

<시간/>

이진 트리가 있다고 가정합니다. 우리는 이진 트리에서 가장 긴 연속 경로의 길이를 찾아야 합니다. 여기서 경로는 증가하거나 감소할 수 있습니다. 예를 들어 [1,2,3,4]와 [4,3,2,1]은 모두 유효한 경로로 간주되지만 경로 [1,2,4,3]은 유효한 경로가 아닙니다.

그렇지 않으면 경로가 자식-부모-자식 순서일 수 있지만 반드시 부모-자식 순서일 필요는 없습니다.

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

가장 긴 연속 경로가 [1, 2, 3] 또는 [3, 2, 1]과 같으므로 출력은 3이 됩니다.

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

solveUtil() 함수를 정의하면 노드가 필요합니다.
노드가 null이면 -
- 반환 { 0, 0 }
왼쪽 =solveUtil(노드의 왼쪽)
왼쪽 =solveUtil(노드의 오른쪽)
한 쌍의 온도 정의 :={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
해결 유틸리티(루트)
반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

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