leetcode 114. 二叉树展开为链表

题目描述

给定一个二叉树,原地将它展开为链表。
例如,给定二叉树


1
/ \
2 5
/ \ \
3 4 6

将其展开为:


1
\
2
\
3
\
4
\
5
\
6

题解

分别递归左右子树变为链表,然后先临时保存右子树,再把右子树指向左子树并清空,最后找到右子树的最后的叶节点,指向临时保存的原右子树

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func flatten(root *TreeNode) {
if root == nil {
return
}
flatten(root.Left)
flatten(root.Right)
tmp := root.Right
root.Right = root.Left
root.Left = nil
for root.Right != nil {
root = root.Right
}
root.Right = tmp
}