二叉搜索树与双向链表

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

思路：

• 1.二叉搜索树，所以他的中序排序就是按大小排序的；
• 2.新建一个集合，将中序排序结果全部加到集合中；
• 3.修改节点的指针

代码：

public TreeNode Convert(TreeNode pRootOfTree) {

      if (pRootOfTree == null) {
          return pRootOfTree;
      }

      ArrayList<TreeNode> list = new ArrayList<>();
      // 中序排序，将所有节点加入到集合中
      getOrderedList(pRootOfTree, list);

      return modify(list);

  }
  // 修改各节点的指针
  private TreeNode modify(ArrayList<TreeNode> list) {
      int len = list.size();
      TreeNode node = list.get(0);
      // 第一个节点的左节点为空
      node.left = null;
      TreeNode first = node;
      for (int i = 1; i < len; i++) {
          // 节点右节点指向当前节点
          node.right = list.get(i);
          // 节点右移至当前节点
          node = node.right;
          // 节点左节点关联前一个节点
          node.left = list.get(i-1);
      }
      // 最后节点的右节点为空
      node.right = null;
      return first;
  }

  private void getOrderedList(TreeNode pRootOfTree, ArrayList<TreeNode> list) {

      if (pRootOfTree.left != null) {
          getOrderedList(pRootOfTree.left,list);
      }

      list.add(pRootOfTree);

      if (pRootOfTree.right != null){
          getOrderedList(pRootOfTree.right, list);
      }
  }