JZ26 二叉搜索树与双向链表

描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

要求：空间复杂度O(1)（即在原树上操作），时间复杂度O(n)。

注意:

1. 要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2. 返回链表中的第一个节点的指针
3. 函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构

示例

输入：

{10,6,14,4,8,12,16}

返回值：

From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;

解析

首先，树的问题离不开树的遍历，本题的树是二叉搜索树，特点为左孩子节点值 < 当前节点值 < 右孩子节点值，即左中右，与二叉树的中序遍历顺序相同！也就是说，只要进行中序遍历，就能遍历二叉搜索树中由小到大的节点！

在一开始写的时候，我没有注意到空间复杂度为O(1)的要求，即不能开辟新的空间；此时的思路是利用一个节点数组随着中序遍历保存节点，这样遍历完后数组中的顺序就是链表的节点顺序，再进行头尾指针的调整即可。

代码清单

import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    private ArrayList<TreeNode> nodeList = new ArrayList<>();
    public TreeNode Convert(TreeNode pRootOfTree) {
        MidOrder(pRootOfTree);
        int num = nodeList.size();
        if(num == 0)
            return null;
        // 数组最后一个是尾结点，单独设置后继为null
        for(int i = 0;i < num-1;i++){
            nodeList.get(i).right = nodeList.get(i+1);
        }
        nodeList.get(num-1).right = null;
        // 数组第一个是头结点，单独设置前驱为null
        for(int i = num-1;i > 0;i--){
            nodeList.get(i).left = nodeList.get(i-1);
        }
        nodeList.get(0).left = null;
        return nodeList.get(0);
    }
    
    public void MidOrder(TreeNode node){
        if(node == null)
            return;
        MidOrder(node.left);
        nodeList.add(node);
        MidOrder(node.right);
    }
}

这种方式简单且容易理解，但不符合题目要求，所以就有了第二种方式！

由于不能开辟新的空间，就说明我们需要随着树的遍历调整指针关系。但在普通的遍历中，我们只能获得当前正在遍历的节点的信息，这就需要引入一个 pre 变量，用于指向遍历到的当前节点的上一个节点，这样在到达每个节点时，都能通过操作 pre 节点和当前节点构造链表。

代码清单

public class Solution {
    private TreeNode pre = null;
    private TreeNode head = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null)
            return null;
        Convert(pRootOfTree.left);
        if( head == null){
            // 开始执行的第一个节点就是头结点！
            head = pRootOfTree;
        }
        if( pre != null){
            // 上一个设置为前驱
            pRootOfTree.left = pre;
            // 当前是上一个的后继
            pre.right = pRootOfTree;
        }
        // 调整 pre，继续走
        pre = pRootOfTree;
        Convert(pRootOfTree.right);
        return head;
    }
}

不过还有一个点需要注意，由于中序遍历过程对于二叉搜索树来说是由小到大的，也就是说最后 pre 会指向链表末尾，即值最大的节点，与题目要求返回链表头结点的要求不符；这就需要另外引入一个变量 head，保存遍历时的第一个节点，也就是链表的头结点。

上述问题也有另一种解决方式，即按左中右的顺序遍历，pre 会指向链表末尾，那么按照右中左的顺序遍历，pre 不就可以指向链表头部了？这种方式更加巧妙，代码量也更少，不过这里就不列出来了。

总结

本题的破局之处是二叉搜索树的结构符合中序遍历的顺序，只要进行中序遍历，就能从小到大地访问二叉搜索树的节点！