题目

image.png

思路

  • 由于要进行排序处理，而且它是二叉搜索树，因此中序遍历的就是有序，所以我们必然使用中序遍历来完成转换

    • 递归方式，在中序遍历的递归中进行处理让前一个节点指向后一个节点，并且需要额外头尾节点记录

    • 遍历方式，使用中序遍历记录下所有节点，在遍历节点依次连接起来

      代码

      ```java //1.使用递归方式 Node prev , head; public Node treeToDoublyList(Node root) { if (root == null) return root; recur(root); head.left = prev; prev.right = head; return head; }

      public void recur(Node root) { if (root == null) return; recur(root.left);
      root.left = prev; if (prev != null) 

      1.    prev.right = root;

      else

      1.    head = root; //当前面没有节点，就说明是头结点

      prev = root; recur(root.right); }

      //2.使用遍历的方式 Queue queue = new LinkedList<>(); public Node treeToDoublyList(Node root) { if(root == null) return root; recur(root); Node head = queue.poll(); Node p = head, q = null; while(!queue.isEmpty()) {

      1.    q = queue.poll();
      2.    p.right = q;
      3.    q.left = p;
      4.    p = q;

      } if(q == null) {

      1.    head.left = head;
      2.    head.right = head;

      } else {

         head.left = q;
   q.right = head;

      } return head; }

      public void recur(Node root) { if(root == null) return; recur(root.left); queue.offer(root); recur(root.right); }

``` 二叉搜索树与双向链表