题目

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

思路 + 代码

二叉搜索树的中序遍历即为一个排序的顺序，按照该顺序依次构建双向链表即可。

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
35
36
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    private TreeNode firstHead = null;
    private TreeNode preHead = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null)
            return null;
        // 整个遍历过程与中序遍历相同
        // 遍历到最左侧叶子节点，即最小的叶子节点
        Convert(pRootOfTree.left);
        // 第一次将头指针指向最小叶子节点（处理中间节点pRootOfTree）
        if(preHead==null){
            preHead = pRootOfTree;
            firstHead = pRootOfTree;
        }else{
            pRootOfTree.left=preHead;
            preHead.right = pRootOfTree;
            preHead = pRootOfTree;
        }
        // 右节点
        Convert(pRootOfTree.right);
        return firstHead;
    }
}