【面试题26-二叉搜索树与双向链表】

剑指offer第二十六题。

题目描述

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

解题思路

我们直到二叉搜索树的一个重要性质就是中序遍历是有序序列，那么本体要求转换为一个有序的双向链表，那么我们就可以通过中序遍历，将遍历到的结点以双向链表的形式串联起来。

我的答案

public class Solution {
    //定义两个指针，分别表示双向链表的头和尾
    //只是指针，不是新创建结点，符合题意
    TreeNode head = null;
    TreeNode tail = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        //就是一个中序遍历，然后将中序遍历出来的结果以双向链表的形式串起来即可
        if(pRootOfTree == null){
            return null;
        }
        
        Convert(pRootOfTree.left);
        
        //串成双向链表
        if(head == null){
            head = tail = pRootOfTree;
        }else{
            tail.right = pRootOfTree;
            pRootOfTree.left = tail;
            tail = pRootOfTree;
        }
        
        Convert(pRootOfTree.right);
        
        return head;
    }
}