AcWing 49. 非常极其简短好理解的解法

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 49. 非常极其简短好理解的解法原题链接中等

作者：

秃秃秃 , 2020-01-17 14:22:44 , 所有人可见 , 阅读 5072

84

34

题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

要求不能创建任何新的结点，只能调整树中结点指针的指向。

注意：

需要返回双向链表最左侧的节点。

样例

思路

就在中序递归遍历的基础上改了一点点，用一个pre指针保存中序遍历的前一个结点。
因为是中序遍历，遍历顺序就是双线链表的建立顺序；
每一个结点访问时它的左子树肯定被访问过了，所以放心大胆的改它的left指针，不怕树断掉；
同理，pre指向的结点保存的数肯定小于当前结点，所以其左右子树肯定都访问过了，所以其right指针也可以直接改。

最后需要一直向左找到双向链表的头结点。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    TreeNode* pre = NULL;

    TreeNode* convert(TreeNode* root) {
        dfs(root);
        while(root && root->left) root = root->left;
        return root;
    }
    void dfs(TreeNode* root){
        if(!root) return;
        dfs(root->left);

        root->left = pre;
        if(pre) pre->right = root;
        pre = root;

        dfs(root->right);
    }
};

28 评论

RainDaydream 2023-04-08 19:08

这么写为啥不对呢

class Solution {
public:

    TreeNode* convert(TreeNode* root) {
        if(!root) return NULL;

        TreeNode *l=convert(root->left);
        TreeNode* cur=l;
        while(cur&&cur->right) cur=cur->right;
        root->left=cur;
        if(cur) cur->right=root;

        TreeNode* r=convert(root->right);
        root->right=r;
        if(!r) r->left=root;

        if(l) return l;
        return root;
    }
};

doragd 2022-04-16 22:17

其实可以再用一个head指针，if(pre) pre->right = root; else head = root; 也就是说当pre为空时，当前结点就是头结点

秃秃秃 2022-10-09 18:02

嗯呢，也可以的

流水线上的打字员 2022-03-02 19:25

结点指针符不符合题目中的要求啊，题目中要求是不允许创建新结点，但是这是结点指针。。。

秃秃秃 2022-10-09 18:07

创建新结点是要new一个新结点，节点指针不是创建新结点哈

想当开心果呀 2022-01-13 23:23

怎么感觉像是创建的新的节点一样。

Critic 2022-03-01 09:39

是创建了pre节点，与题意不符了。

安青柚 2021-12-07 08:44

实在是太帅了!!!

Si1ence 2021-07-18 21:05

果然排第一的题解就是无敌的存在！

七品要员 2021-05-15 20:01

大佬中序遍历玩明白了👍

飞飞爱编程 2021-04-20 18:03

强强强，大佬就是牛X，奈何本人没文化，一句牛逼行天下！

div 2021-02-16 22:57

同样的代码，acwingAC了，lc样例空指针异常，为什么啊

Eternity_7 2021-03-25 17:42

lc的题目需要把头尾连接起来

有心人 2021-08-15 23:00

// 二叉搜索树 中序遍历 递增
class Solution {
public:
    TreeNode *pre = NULL, *head = NULL;

    TreeNode* convert(TreeNode* root) {
        if (!root) return NULL;
        dfs(root);

        // leetcode 是 循环链表,  要加上 这里
        // 循环链表 首尾相连, pre 最后在 链表尾结点
        //head->left = pre, pre->right = head;

        return head;
    }

    void dfs(TreeNode* cur) { // 此处 用 cur 更贴切
        if (!cur) return;

        dfs(cur->left); // 中序遍历: 左中右

        if (!pre) head = cur; // pre为NULL, 找到头结点
        else { // 存在 pre, 将 pre 与 cur 左右 互连 
            pre->right = cur; 
            cur->left = pre;
        }

        pre = cur; // 更新 pre

        dfs(cur->right);
    }
};