为何修改递归返回的pair会导致二叉树最长连续序列II求解失败？

我正在解决LeetCode 549的二叉树最长连续序列II问题，目标是找出二叉树中最长的连续路径（递增或递减）长度，路径可双向延伸（子节点→父节点→子节点），而非仅向下。

错误解法 #

class Solution {
public:
    int maxLen = 0;

    pair<int, int> toNode(TreeNode *node) {
        if (!node) return {0, 0};

        pair<int, int> 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;
    }
};

正确解法 #

class Solution {
public:
    int maxLen = 0;
    pair<int, int> toNode(TreeNode *node){
        if(!node)return {1, 1};
        pair<int, int>linc(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;
    }
};

问题 #

为何第一个版本会失败？我仅根据条件递增pair的linc.first或linc.second，且未在其他地方使用该返回对，原以为这种修改是安全的。

可复现测试用例 #

输入：[3, null, 4, null, 1, null, 2]
预期结果：2
错误解法返回：3

错误原因分析 #

第一个版本有两个核心逻辑错误：

1. 条件判断与pair成员的对应关系完全搞反 #

我们定义递归返回的pair<int, int>为{inc, dec}：

• inc：以当前节点为起点，向下递增（子节点值=父节点值+1）的最长路径长度；
• dec：以当前节点为起点，向下递减（子节点值=父节点值-1）的最长路径长度。

但第一个版本的判断逻辑完全颠倒：

• 当左子节点值=当前节点值+1（即node->left->val -1 == node->val），此时当前节点的inc应该继承左子节点的inc并+1，但代码中却修改了linc.second（对应子节点的dec值）；
• 当左子节点值=当前节点值-1（即node->left->val +1 == node->val），此时当前节点的dec应该继承左子节点的dec并+1，但代码中却修改了linc.first（对应子节点的inc值）。

这种颠倒直接导致路径长度的计算完全错误。

2. 修改递归返回的子节点路径值，混淆了子节点与当前节点的路径关系 #

第一个版本直接修改从子节点递归返回的linc和rdec对象，再用修改后的值计算当前节点的inc和dec。这种操作相当于把子节点的路径长度和当前节点的路径长度混为一谈，破坏了递归返回值的语义——子节点的返回值仅代表以子节点为起点的路径长度，不能直接修改来表示当前节点的路径长度。

而正确版本的做法是：

• 保留子节点的原始返回值，不做修改；
• 单独定义变量（lic、lid等），根据条件计算当前节点能从子节点继承的路径长度；
• 最后基于这些变量计算当前节点的inc和dec，逻辑清晰且语义明确。

内容的提问来源于stack exchange，提问作者fortnight learner