Đường ZigZag dài nhất trong Cây nhị phân trong C ++

Giả sử chúng ta có gốc cây nhị phân, đường dẫn ZigZag cho cây nhị phân được định nghĩa như sau -

Chọn bất kỳ nút nào trong cây nhị phân và một hướng (phải hoặc trái).
Nếu hướng hiện tại là bên phải thì di chuyển về phía nút con bên phải của nút hiện tại, ngược lại thì di chuyển về phía nút con bên trái.
Sau đó, thay đổi hướng từ phải sang trái hoặc ngược lại.
Lặp lại bước thứ hai và thứ ba cho đến khi chúng ta không thể di chuyển trong cây.

Ở đây độ dài Zigzag được định nghĩa là số lượng nút được truy cập - 1. (Một nút duy nhất có độ dài bằng 0). Chúng ta phải tìm đường ZigZag dài nhất có trong cây đó. Vì vậy, ví dụ, nếu cây giống như -

Đầu ra sẽ là 3, là (Phải, Trái, Phải)

Để 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 phương thức được gọi là dfs (), phương thức này sẽ bắt nguồn từ root và leftB
nếu gốc là null, thì trả về -1
nếu gốc chỉ là một nút trong cây, thì trả về 0
leftV:=dfs (left of root, true) và rightV:=dfs (right of root, false)
ret:=max của ret và (1 + max của leftV và rightV)
nếu leftB không phải là 0 thì trả về 1 + rightV, ngược lại trả về 1 + leftV
Từ phương thức chính, đặt ret:=0
gọi dfs (root, true) và gọi dfs (root, false)
trả lại ret

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau đây để 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 = 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));
}

Đầu vào

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