【dfs 中序】 offer36 二叉搜索树与双向链表

题目

将一个二叉搜索树转换成循环双向链表

思路

二叉搜索树按中序遍历出就是升序序列，再标注一个前驱节点就可以进行链表的连接。

代码

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; } } Node pre,head; public Node treeToDoublyList(Node root) { if(root==null) return null; dfs(root); //得到头尾结点，将头尾连接 // 遍历结束后，head是头，pre是尾 head.left = pre; pre.right = head; return head; } public void dfs(Node cur){ if(cur==null) return; //中序遍历的顺序 //左 dfs(cur.left); //根 if(pre!=null) { pre.right = cur; }//在第一步的时候，pre为空，用head记录整个序列中最小节点 else{ head = cur; } cur.left = pre; pre = cur; //右 dfs(cur.right); }