C++의 이진 트리에서 가장 긴 지그재그 경로

<시간/>

이진 트리 루트가 있다고 가정하고 이진 트리의 ZigZag 경로는 다음과 같이 정의됩니다. -

이진 트리의 노드와 방향(오른쪽 또는 왼쪽)을 선택합니다.
현재 방향이 오른쪽이면 현재 노드의 오른쪽 자식으로 이동하고 그렇지 않으면 왼쪽 자식으로 이동합니다.
그런 다음 방향을 오른쪽에서 왼쪽으로 또는 그 반대로 변경합니다.
나무에서 움직일 수 없을 때까지 두 번째와 세 번째 단계를 반복합니다.

여기서 지그재그 길이는 방문한 노드 수 - 1로 정의됩니다. (단일 노드의 길이는 0입니다). 우리는 그 트리에 포함된 가장 긴 지그재그 경로를 찾아야 합니다. 예를 들어 트리가 다음과 같다면 -

출력은 (Right, Left, Right)

와 같이 3이 됩니다.

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

dfs()라는 메소드를 정의하십시오. 이것은 root를 취하고 leftB
루트가 null이면 -1을 반환합니다.
루트가 트리의 한 노드일 경우 0을 반환합니다.
leftV :=dfs(루트의 왼쪽, true) 및 rightV :=dfs(루트의 오른쪽, false)
ret :=ret의 최대값 및 (1 + leftV 및 rightV의 최대값)
leftB가 0이 아니면 1 + rightV를 반환하고, 그렇지 않으면 1 + leftV를 반환
기본 방법에서 ret :=0
을 설정합니다.
dfs(root, true) 호출 및 dfs(root, false) 호출
리턴 렛

예시(C++)

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

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = right = NULL;
   }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
         } else {
            q.push(temp->left);
         }
         if(!temp->right){
            if(val != NULL)
               temp->right = new TreeNode(val);
            else
               temp->right = new TreeNode(0);
            return;
            }else{
               q.push(temp->right);
            }
         }
   }
   TreeNode *make_tree(vector<int> v){
      TreeNode *root = new TreeNode(v[0]);
      for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
   public:
   int ret;
   int dfs(TreeNode* root, bool leftB){
      if(!root) return -1;
      if(!root->left && !root->right) return 0;
      int leftV = dfs(root->left, true);
      int rightV = dfs(root->right, false);
      ret = max(ret, 1 + max(leftV, rightV));
      if(leftB) return 1 + rightV;
         return 1 + leftV;
   }
   int longestZigZag(TreeNode* root) {
      ret = 0;
      dfs(root, true);
      dfs(root, false);
      return ret;
   }
};
main(){
   vector<int> v = {1,NULL,1,1,1,NULL,NULL,1,1,NULL,1,NULL,NULL,NULL,1,NULL,1};
   TreeNode *root = make_tree(v);
   Solution ob;
   cout << (ob.longestZigZag(root));
}

입력

[1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]