本文共 1098 字，大约阅读时间需要 3 分钟。

1. 本题知识点

树

2. 题目描述

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

3. 解题思路

中序遍历二叉搜索树，然后用一个 ArrayList 类保存遍历的结果，最后再来修改指针。

4. 代码

public class TreeNode {
       int val = 0;    TreeNode left = null;    TreeNode right = null;    public TreeNode(int val) {
           this.val = val;    }}

import java.util.ArrayList;public class Solution {
       ArrayList
   
     list = new ArrayList<>();    public TreeNode Convert(TreeNode pRootOfTree) {
           if (pRootOfTree == null) {
               return null;        }        InOrderTraverse(pRootOfTree);        // 修改指针        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);    }    // 中序遍历二叉搜索树，然后用一个 ArrayList 类保存遍历的结果    public void InOrderTraverse(TreeNode pRootOfTree) {
           if (pRootOfTree.left != null) {
               InOrderTraverse(pRootOfTree.left);        }        list.add(pRootOfTree);        if (pRootOfTree.right != null) {
               InOrderTraverse(pRootOfTree.right);        }    }}
   

转载地址：http://gbjvb.baihongyu.com/