LeetCode 114. 二叉树展开为链表
题目描述
思路分析
迭代 + 栈
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func flatten(root *TreeNode) {
if root == nil {
return
}
stack := []*TreeNode{root}
var pre *TreeNode
for len(stack) > 0 {
cur := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if pre != nil {
pre.Right = cur
pre.Left = nil
}
pre = cur
// 右子树先入栈，左子树后入栈
if cur.Right != nil {
stack = append(stack, cur.Right)
}
if cur.Left != nil {
stack = append(stack, cur.Left)
}
}
}
- 时间复杂度：O(n)，每个节点访问一次。
- 空间复杂度：O(n)，递归或栈的深度最大为 n。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func flatten(root *TreeNode) {
// 记录前一个节点
var pre *TreeNode
var dfs func(*TreeNode)
dfs = func(cur *TreeNode) {
if cur == nil {
return
}
// 先右后左的逆前序遍历
dfs(cur.Right)
dfs(cur.Left)
// 修改指针
cur.Right = pre
cur.Left = nil
pre = cur
}
dfs(root)
}
- 时间复杂度：O(n)，每个节点访问一次。
- 空间复杂度：O(n)，递归或栈的深度最大为 n。
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！