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

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

概述

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);
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/