1. /*
  2. // Definition for a Node.
  3. class Node {
  4.     public int val;
  5.     public Node left;
  6.     public Node right;
  8.     public Node() {}
  10.     public Node(int _val) {
  11.         val = _val;
  12.     }
  14.     public Node(int _val,Node _left,Node _right) {
  15.         val = _val;
  16.         left = _left;
  17.         right = _right;
  18.     }
  19. };
  20. */
  21. class Solution {
  22.     Node head, pre;
  23.     public Node treeToDoublyList(Node root) {
  24.         if(root==null) return null;
  25.         dfs(root);
  27.         pre.right = head;
  28.         head.left =pre;//进行头节点和尾节点的相互指向，这两句的顺序也是可以颠倒的
  30.         return head;
  31.     }
  33.     public void dfs(Node cur){
  34.         if(cur==null) return;
  35.         dfs(cur.left);
  37.         cur.left = pre;//pre是否为null对这句没有影响,且这句放在上面两句if else之前也是可以的。
  38.         //pre用于记录双向链表中位于cur左侧的节点，即上一次迭代中的cur,当pre==null时，cur左侧没有节点,即此时cur为双向链表中的头节点
  39.         if(pre==null) head = cur;
  40.         //反之，pre!=null时，cur左侧存在节点pre，需要进行pre.right=cur的操作。
  41.         else pre.right = cur;
  43.         pre = cur;//pre指向当前的cur
  45.         dfs(cur.right);//全部迭代完成后，pre指向双向链表中的尾节点
  46.     }
  47. // 作者：jyd
  48. // 链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/solution/mian-shi-ti-36-er-cha-sou-suo-shu-yu-shuang-xian-5/
  50. }

剑指 Offer 36. 二叉搜索树与双向链表