[题目链接]

preview -> 题目难度:简单
给一个二叉搜索树, 让你转换成一个双向链表

题解

由于是一个二叉搜索树, 所以中序遍历刚好就是满足顺序的, 要处理的其实就是指针的关系, 先写一个中序遍历, 然后每一个循环中要做的就是,先把前一个节点的后指针指向当前节点, 然后把当前节点的前指针指向前一个节点,在实际操作中, 先写一个中序遍历的函数, 然后加上函数的处理的关系, 然后直接进入主函数, 处理头节点的关系, 头节点就是直接用head存, 然后也是绑定两个指针

源码

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
32
33
34
class Solution {
    Node pre;
    Node head;
    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return head;
        }

        dfs(root);
        head.left = pre;
        pre.right = head;



    }

    void dfs(Node root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        // 本层
        if (pre != null) {
            pre.right = root;
        }else {
            head = root;
        }
        root.left = pre;
        pre = root;


        dfs(root.right);
    }
}