题目描述

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

答案

import java.util.*;
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        ArrayList<TreeNode> list = new ArrayList<>();
        midOrder(pRootOfTree,list);
        for(int i = 0;i<list.size()-1;i++){
            list.get(i).right = list.get(i+1);
            list.get(i+1).left = list.get(i);
        }
        return list.get(0);
    }
    public void midOrder(TreeNode pRootOfTree,ArrayList<TreeNode>list){
        if(pRootOfTree.left != null){
            midOrder(pRootOfTree.left,list);
        }
        list.add(pRootOfTree);
        if(pRootOfTree.right != null){
            midOrder(pRootOfTree.right,list);
        }
    }
}

解析

难点在于不能新建结点,如果我们改变左右结点就会遗失一部分树的结构,因此我们使用集合来存储结点之间的顺序,一个排序的双向链表,我们可以想到使用中序遍历(左根右)来实现。

midOrder函数就是帮我们实现往集合里按中序遍历顺序插入的函数。

看看具体的思路,首先,如果根节点的左边有结点,我们就重复递归直到为空,然后将最左边的子节点加进list,回退,将根节点加进list,然后向右遍历,进到下一层重复这个步骤,左边,中间,右边。

加入之后对列表进行一次遍历,根据下标将左右指针重新连接即可


醉后不知天在水,满船清梦压星河