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) }
