Я пытаюсь решить самую длинную проблему последовательной последовательной последовательности II (LeetCode 549). Цель состоит в том, чтобы найти длину самого длинного последовательного пути (увеличивающегося или уменьшения) в двоичном дереве. Путь может идти в обоих направлениях (ребенок → родитель → ребенок), а не только вниз. Вот код, который не работает: < /p>
class Solution {
public:
int maxLen = 0;
pair toNode(TreeNode *node) {
if (!node) return {0, 0};
pair linc(0, 0), rdec(0, 0);
if (node->left) {
linc = toNode(node->left);
if (node->left->val - 1 == node->val) {
linc.second++;
}
if (node->left->val + 1 == node->val) {
linc.first++;
}
}
if (node->right) {
rdec = toNode(node->right);
if (node->right->val - 1 == node->val) {
rdec.second++;
}
if (node->right->val + 1 == node->val) {
rdec.first++;
}
}
int inc = max(1, max(linc.first, rdec.first));
int dec = max(1, max(linc.second, rdec.second));
maxLen = max(maxLen, inc + dec - 1);
return {inc, dec};
}
int longestConsecutive(TreeNode* root) {
toNode(root);
return maxLen;
}
};
< /code>
Теперь эта версия не дает правильного результата для всех тестовых случаев. Однако, когда я рефактирую его, как ниже - вычислять вкл и uc отдельно, не мутируя рекурсивные возвратные значения - он работает нормально: < /p>
class Solution {
public:
int maxLen = 0;
pair toNode(TreeNode *node){
if(!node)return {1, 1};
pairlinc(0, 0), rdec(0, 0);
int lic=0, lid=0, ric=0, rid=0;
if(node->left){
linc = toNode(node->left);
if(node->left->val == node->val-1)lid = linc.second+1;
if(node->left->val == node->val+1)lic = linc.first+1;
}
if(node->right){
rdec = toNode(node->right);
if(node->right->val == node->val-1)rid = rdec.second+1;
if(node->right->val == node->val+1)ric = rdec.first+1;
}
int inc = max(1, max(lic , ric));
int dec = max(1, max(lid, rid));
int cur = inc + dec - 1;
maxLen = max(cur, maxLen);
return {inc, dec};
}
int longestConsecutive(TreeNode* root) {
toNode(root).first;
return maxLen;
}
};
< /code>
Вопрос < /strong>
Почему первая версия стерла, даже если я увеличиваю значения пары (linc.first ++ или linc.second ++) на основе условий? Я явно не использую возвращенную пару где -либо еще, поэтому я ожидал, что эта мутация будет безопасной.[3, null, 4, null, 1, null, 2]
< /code>
ожидаемый результат: 2
my -код возвращает: 3
demo < /p>
Подробнее здесь: https://stackoverflow.com/questions/796 ... olution-in
