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

class Solution {
    Node pre,head;
    //中序遍历 + 存储上个节点
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    //使用中序遍历完成全过程
    void dfs(Node curr){
        if(curr == null) return;
        dfs(curr.left);
        //判断前驱节点是否为空
        if(pre != null){
            //左指针指向前驱
            pre.right = curr;
        }else{
            //若不存在前驱节点 则当前节点为头节点，记录当前节点
            head = curr;
        }
        curr.left = pre;
        pre = curr;
        dfs(curr.right);
    }
}