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

题目

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

为了让您更好地理解问题，以下面的二叉搜索树为例：

01

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

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

02

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

来源：力扣（LeetCode）

分析

题解

由于没有官方没有 Swift 的用例，这里自己写了用例来测试

代码

var head: TreeNode?, last: TreeNode?

func treeToDoublyList(root: TreeNode) -> TreeNode {
    handle(root: root)
    last?.right = head
    head?.left = last
    return root
}

func handle(root: TreeNode) -> TreeNode {
    if let left = root.left {
        if let rightOfLeft = left.right {
            let node = handle(root: rightOfLeft)
            root.left = node
            node.left = left
            node.right = root
        }
        
        if let leftOfLeft = left.left, leftOfLeft.left == nil {
            leftOfLeft.right = left
            head = leftOfLeft
        }
    }
    
    if let right = root.right {
        if let leftOfRight = right.left {
            let node = handle(root: leftOfRight)
            root.right = node
            node.right = right
            node.left = root
        }
        
        if let rightOfRight = right.right, rightOfRight.right == nil {
            rightOfRight.left = right
            last = rightOfRight
        }
    }
    
    return root
}

用例

let t1 = TreeNode(1)
let t2 = TreeNode(2)
let t3 = TreeNode(3)
let t4 = TreeNode(4)
let t5 = TreeNode(5)
let t6 = TreeNode(6)
let t7 = TreeNode(7)

t4.left = t2
t4.right = t6

t2.left = t1
t2.right = t3

t6.left = t5
t6.right = t7

let arr = [t1, t2, t3, t4, t5, t6, t7]

func log(root: TreeNode) {
    if let left = root.left {
        print("\(root.val)左：\(left.val)")
    }
    else {
        print("\(root.val)左：nil")
    }
    
    if let right = root.right {
        print("\(root.val)右：\(right.val)")
    }
    else {
        print("\(root.val)右：nil")
    }
}

arr.forEach { log(root: $0) }

print("=== 双向转换 ===")
treeToDoublyList(root: t4)

arr.forEach { log(root: $0) }

输出：

1左：nil
1右：nil
2左：1
2右：3
3左：nil
3右：nil
4左：2
4右：6
5左：nil
5右：nil
6左：5
6右：7
7左：nil
7右：nil
=== 双向转换 ===
1左：7
1右：2
2左：1
2右：3
3左：2
3右：4
4左：3
4右：5
5左：4
5右：6
6左：5
6右：7
7左：6
7右：1