剑指offer36 二叉搜索树和双向链表

发表于 | 分类于 |
字数统计: 356 | 阅读时长 ≈ 1

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

题意

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向

解法

中序遍历二叉树，得到的就是按顺序排列的序列
考虑中序遍历的递归处理，先处理左子树，再处理右子树
左子树处理完了，就可以让当前节点的左节点指向左子树
同时让左子树的最后一个节点指向当前节点
关键步骤就在上述两句中
再处理右子树
现在的关键在于需要知道当前的最后一个节点，因此需要把它作为函数传递的一个参数(或是设置全局变量也可以)
每次记录当前的最后一个节点
递归完成整个过程

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    Node* ans;
    void dfs(Node* root, Node** lastNode) {
        if (!root) return;
        if (root -> left) {
            dfs(root -> left, lastNode);
        }
        root -> left = *lastNode;
        if (*lastNode != nullptr) {
            // cout << (*lastNode) -> val << endl;
            (*lastNode) -> right = root;
        }
        *lastNode = root;
        if (root -> right) {
            dfs(root -> right, lastNode);
        }
    }
    Node* treeToDoublyList(Node* root) {
        if(!root) return root;
        Node* lastNode = nullptr;
        dfs(root, &lastNode);
        Node* first = lastNode;
        while(first -> left != nullptr) {
            first = first -> left;
        }
        first -> left = lastNode;
        lastNode -> right = first;
        return first;
    }
};