剑指 Offer 36. 二叉搜索树与双向链表

    
        标签：
        
            剑指 Offer
        
    发布于：2022-02-26 09:59:30
    编辑于：2022-02-26 10:11:25
    浏览量：917

概述

https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/

https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/

中序遍历

下面的代码 WA，看出来问题了吗？

class Solution {
public:
    vector<Node*> nodes;
    Node* treeToDoublyList(Node* root) {
        if (!root) return nullptr;
        travel(root);
        for (int i = 0; i < nodes.size(); i ++) {
            int prevIdx = (i - 1) % nodes.size();
            int nextIdx = (i + 1) % nodes.size();
            nodes[i]->left = nodes[prevIdx];
            nodes[i]->right = nodes[nextIdx];
        }
        return nodes[0];
    }

    void travel(Node* root) {
        if (!root) return;
        travel(root->left);
        nodes.push_back(root);
        travel(root->right);
    }
};

是 size() 的类型问题，将其换成 int：

class Solution {
public:
    vector<Node*> nodes;
    Node* treeToDoublyList(Node* root) {
        if (!root) return nullptr;
        travel(root);
        int n = nodes.size();
        for (int i = 0; i < n; i ++) {
            int prevIdx = (i - 1) % n;
            int nextIdx = (i + 1) % n;
            nodes[i]->left = nodes[prevIdx];
            nodes[i]->right = nodes[nextIdx];
        }
        return nodes[0];
    }

    void travel(Node* root) {
        if (!root) return;
        travel(root->left);
        nodes.push_back(root);
        travel(root->right);
    }
};

结果：addition of unsigned offset，输出索引看了一下，发现第一个 prevIdx 竟然是 -1！

负数取余的锅，C++ 里面余数可以为负数，所以 -1 % 3 = -1。

绝绝子，Python 里面就是正数：

In [2]: -1 % 3
Out[2]: 2

class Solution {
public:
    vector<Node*> nodes;
    Node* treeToDoublyList(Node* root) {
        if (!root) return nullptr;
        travel(root);
        int n = nodes.size();
        for (int i = 0; i < n; i ++) {
            int prevIdx = i - 1;
            if (prevIdx == -1) prevIdx = n - 1;
            int nextIdx = (i + 1) % n;
            nodes[i]->left = nodes[prevIdx];
            nodes[i]->right = nodes[nextIdx];
        }
        return nodes[0];
    }

    void travel(Node* root) {
        if (!root) return;
        travel(root->left);
        nodes.push_back(root);
        travel(root->right);
    }
};

Links: sword-offer-36