剑指offer面试题36：二叉树与双向链表（Java 实现）

115 阅读 0 评论 76 点赞

我是靠谱客的博主野性飞鸟，这篇文章主要介绍剑指offer面试题36：二叉树与双向链表（Java 实现），现在分享给大家，希望可以做个参考。

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

思路：利用中序遍历的方法递归遍历二叉树，把二叉树拆分为左子树、根节点、右子树三部分，再连接起来。第一步先遍历左子树转化为链表，然后把根节点连在左子树的最后节点，然后再递归遍历右子树。

测试用例：

1. 功能测试：完全二叉树；所有节点只有左子树的二叉树；所有节点只有右子树的二叉树；只有一个节点。
2. 特殊测试：输入的根节点为空。

复制代码

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
public class test_thirty_six {
    TreeNode tail = null;  //定义链表的最后一个节点
    TreeNode head = null;  //链表的第一个节点

    public TreeNode Convert(TreeNode pRootOfTree) {
        ConvertSub(pRootOfTree);
        return head;
    }
    //构造一个递归函数中序遍历二叉树
    private void ConvertSub(TreeNode pRootOfTree) {
        if(pRootOfTree==null) return;

        ConvertSub(pRootOfTree.left);    //递归遍历左子树
        if (tail == null) {              //左子树为空
            tail = pRootOfTree;          //根节点即为尾节点
            head = pRootOfTree;
        }
        else {
            tail.right = pRootOfTree;    //把根节点连接到左子树的末尾
            pRootOfTree.left = tail;
            tail = pRootOfTree;          //更新尾节点
        }
        ConvertSub(pRootOfTree.right);   //递归遍历右子树
    }
}