剑指offer（二十六）二叉搜索树与双向链表

点击进入 牛客网题库：二叉搜索树与双向链表

题目描述

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

这个题目首先要弄懂，什么是双向链表

头节点的 right --> 下一个节点
下一个节点的 left --> 头节点
下一个节点的 right --> 下下一个节点

方法一 直接法 用ArrayList+中序遍历

import java.util.ArrayList;

public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            return null;
        }
        ArrayList<TreeNode> list = new ArrayList<>();
        Convert(list, pRootOfTree);
        int size = list.size();
        for(int i = 0; i < size - 1; i++) {
            list.get(i).right = list.get(i+1);
            list.get(i+1).left = list.get(i);
        }
        return list.get(0);
    }
    
    /**
    *
    * 进行中序遍历
    */
    private void Convert(ArrayList<TreeNode> list, TreeNode pRootOfTree) {
        
        if(pRootOfTree.left != null) {
            Convert(list, pRootOfTree.left);
        }
        
        list.add(pRootOfTree);
        
        if(pRootOfTree.right != null) {
            Convert(list, pRootOfTree.right);
        }
    }
}

方法二 正着中序遍历

通过存储 pre 和 root 来进行

pre 交换过程中的缓存节点，在指针修改方向后，就变成下一个节点了
root 交换过程中的头节点

public class Solution {
    TreeNode pre = null;
    TreeNode root = null;
    
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            return null;
        }
        
        Convert(pRootOfTree.left);
        
        if(root == null) {
           root =  pRootOfTree;
        }
        
        if(pre == null) {
            pre = pRootOfTree;
        } else {
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
            pre = pRootOfTree;
        }
        
       Convert(pRootOfTree.right);
        
        return root;
    }
   
}

方法三

反向操作 中序遍历，通过存储一个节点来进行操作，比上次少用来了个 root 节点存储

public class Solution {
    TreeNode pre = null;
    
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            return null;
        }
        Convert(pRootOfTree.right);
        
        if(pre == null) {
             pre = pRootOfTree;
        } else {
            pRootOfTree.right = pre;
            pre.left = pRootOfTree;
            pre = pRootOfTree;
        }
        
        Convert(pRootOfTree.left);
        
        return pre;
    }
   
}