Đường Đi ZigZag Dài Nhất Trong Cây Nhị Phân Trong C++

Giả sử chúng ta có cây nhị phân root. Đường đi ZigZag được định nghĩa như sau:

Chọn bất kỳ nút nào và một hướng (trái hoặc phải).
Nếu hướng hiện tại là phải thì đi sang con phải, ngược lại sang con trái.
Đổi hướng (trái ↔ phải).
Lặp lại bước 2 và 3 cho đến khi không thể di chuyển nữa.

Độ dài ZigZag = số nút đã thăm - 1 (nút đơn lẻ có độ dài 0). Tìm đường đi ZigZag dài nhất trong cây.

Ví dụ cây như hình → đầu ra 3 (Right, Left, Right).

Để giải quyết, chúng ta làm theo các bước:

Định nghĩa dfs(root, leftB): nếu root null trả về -1; nếu root là lá trả về 0.
leftV = dfs(root->left, true); rightV = dfs(root->right, false).
ret = max(ret, 1 + max(leftV, rightV)).
Nếu leftB true trả về 1 + rightV, ngược lại 1 + leftV.
Từ main: ret = 0; gọi dfs(root, true) và dfs(root, false); trả về ret.

Ví dụ (C++)

Hãy xem 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 = 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;
    }
};

int 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]

Đường Đi ZigZag Dài Nhất Trong Cây Nhị Phân Trong C++

Ví dụ (C++)

Đầu vào

Đầu ra