剑指offer36-二叉搜索树和双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这一题主要是利用二叉树的中序遍历来实现，包括递归和栈两种方法，对于链表中的头节点，刚开始是没有遍历到它的前驱节点的，处理方法可以是额外创建一个前驱节点，也可以做一次判断，判断前驱是否为空

递归

这里需要注意的是前驱节点要作为全局变量保存下来

"""
# Definition for a Node.
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
"""
class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root:
            return None
        head=Node(0)
        pre=head
        def inorder(root):
            nonlocal pre	//如果将pre绑定到self上就不需要额外声明了
            if root.left:
                inorder(root.left)
            pre.right=root
            root.left=pre
            pre=root
            if root.right:
                inorder(root.right)
        inorder(root)
        head.right.left=pre
        pre.right=head.right
        return head.right

栈

/**
 * // Definition for a Node.
 * function Node(val,left,right) {
 *    this.val = val;
 *    this.left = left;
 *    this.right = right;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
var treeToDoublyList = function(root) {
    if(!root){
        return null;
    }
    let head=new Node(0,null,null),
        pre=head,
        tail=null,
        stack=[],
        cur=root;
    while(stack.length>0||cur){
        while(cur){
            stack.push(cur);
            cur=cur.left
        }
        cur=stack.pop();
        tail=cur;
        pre.right=cur;
        cur.left=pre;
        pre=cur;
        cur=cur.right;
    }
    head.right.left=tail;
    tail.right=head.right;
    return head.right;
};