二叉搜索树与双向链表

---

题目：

题解：

1、中序遍历

• 解题思路：

  • 

• 复杂度分析：

  • 时间复杂度 O(N) ： N 为二叉树的节点数，中序遍历需要访问所有节点。
  • 空间复杂度 O(N) ： 最差情况下，即树退化为链表时，递归深度达到 N，系统使用 O(N) 栈空间。

• 代码：

  class Node {
      public int val;
      public Node left;
      public Node right;
  
      public Node() {}
  
      public Node(int _val) {
          val = _val;
      }
  
      public Node(int _val,Node _left,Node _right) {
          val = _val;
          left = _left;
          right = _right;
      }
  };
  
  class Solution {
      // pre前驱节点，head头节点
      Node pre, head;
      public Node treeToDoublyList(Node root) {
          // 这里必须判断，否则会报错，因为head是null，没有left
          if (root == null) return null;
          // 中序遍历，并将除了首尾节点循环双连接的其余节点进行双连接
          dfs(root);
          // 使得首尾节点循环双连接
          head.left = pre;
          pre.right = head;
  
          // 返回头节点即可
          return head;
      }
  
  
      private void dfs(Node cur) {
  
          if (cur == null) return;
          dfs(cur.left);
  
          if(pre != null) {
              pre.right = cur;
  
          }else head = cur;
  
          cur.left = pre;
          pre = cur;
  
          dfs(cur.right);
      }
  }