题目介绍

题目链接

JZ36 二叉搜索树与双向链表

题目描述

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

如：

题目要求及数据范围

数据范围：输入二叉树的结点数0 <= n <= 1000，二叉树中每个结点的值0 <= val <= 1000

要求：空间复杂度为O(1)，时间复杂度O(n)

题目注意事项

要求不能创建新的结点，只能调整树中的结点指向，树中结点的左指针指向前驱，右指针指向后继

返回链表中第一个结点的指针

函数返回的TreeNode，有左右指针，其实可以看成一个双向链表

不用输出双向链表，程序会根据返回值自动打印输出

二叉搜索树性质介绍?

二叉搜索树又称二叉排序树，它具有以下性质：

若它的左子树不为空，则左子树结点的值都小于根结点的值
若它的右子树不为空，则右子树结点的值都大于根结点的值
它的左右子树也是二叉搜索树

题目分析

题目要将一颗二叉搜索树转化为一个有序的双向链表，从上面二叉搜索树的性质不难得出，该二叉搜索树的中序遍历出的结果刚好是从小到大的顺序，题目要求结点的left指针指向前驱，right指针指向后继，故做题思路如下：

将中序遍历的结点根据题目要求链接起来

解题方法

方法一

画图分析过程：

具体步骤如下：

写一个中序遍历的方法，链接结点
中序遍历采用递归实现，所以在方法外侧先定义pre==null，pre标记遍历root时前一个结点
先递归遍历左子树
再让root.left == pre，if(pre != null)时，让pre.right = root
最后递归遍历右子树
题目给出的方法要返回首结点，首结点为该树的最左侧结点，先找到首结点
如果树为空，返回null，如果不为空，如果根的左子树不为空，在以根的左子树为树继续找最左侧的结点
调用上述中序遍历方法
返回首结点

方法二

因为题目给出了结点的最大个数为1000，并且要求空间复杂度为O(1)，所以我们可以将中序遍历的结点存入一个数组中，该数组new空间的大小为1000，因为1000为具体数值，所以空间复杂度也满足O(1)，再遍历数组将数组中的结点链接起来

具体步骤如下：

new空间为1000存放结点的数组
写一个中序遍历将树中所有的结点存入数组中
在题目给出的方法中，先调用上述方法，将结点存入数组中
从index=0开始遍历数组，让array[index+1].left?= array[index]，array[index].right = array[index+1]

代码实现

方法一代码

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
 
    public TreeNode(int val) {
        this.val = val;
 
    }
 
}
*/
public class Solution {
    TreeNode pre = null;
    public void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        root.left = pre;
        if(pre != null){
            pre.right = root;
        }
        pre = root;
        inOrder(root.right);
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        TreeNode head = pRootOfTree;
        while(head.left != null){
            head = head.left;
        }
        inOrder(pRootOfTree);
        return head;
    }
}

方法二代码

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
 
    public TreeNode(int val) {
        this.val = val;
 
    }
 
}
*/
public class Solution {
    TreeNode[] array = new TreeNode[1000];
    int i = 0;
    public void inOrder(TreeNode root){
        if(root != null){
            inOrder(root.left);
            array[i++] = root;
            inOrder(root.right);
        }
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        inOrder(pRootOfTree);
        int index = 0;
        while(array[index+1] != null){
            array[index].right = array[index+1];
            array[index+1].left = array[index];
            index++;
        }
        return array[0];
    }
}