一 题目描述
给定一个二叉树，原地将它展开为链表。
例如，给定二叉树
1
/ \
2 5
/ \ \
3 4 6
将其展开为：
1
\
2
\
3
\
4
\
5
\
6
二 解题思路 - 前序遍历
2.1 思路1
不难看出，最终所求链表就是二叉树前序遍历的结果
1 -> 2 -> 3 -> 4 -> 5 -> 6
于是会想到一种错误的思路：前序遍历二叉树，每遍历一个节点，就设置
right = left, 然后left = null
image.png
上述思路会丢掉旧的 right
改进方案：在设置 right = left之前保存一下旧的 right，并将旧的 right 嫁接到最右下角
image.png
image.png
2.2 思路1 - 前序遍历 - 递归实现
- 核心代码如下
/// 前序遍历- 递归遍历
- (void)flatten:(TreeNode *)root {
if (root == nil) {
return;
}
if (root.left != nil) {
// 保留之前的right
TreeNode *oldRight = root.right;
// 将left嫁接到right
root.right = root.left;
// 清空left
root.left = nil;
// 将旧的right嫁接到root的最右下角
TreeNode *rightMost = root;
while (rightMost.right != nil) {
rightMost = rightMost.right;
}
rightMost.right = oldRight;
}
[self flatten:root.right]; // 依次递归遍历右节点
}
时间复杂度O(n)，空间复杂度O(n)
- 运行结果如下
2019-11-30 17:35:57.465116+0800 09_Tree[18483:712676] 1
2019-11-30 17:35:57.465311+0800 09_Tree[18483:712676] 2
2019-11-30 17:35:57.465405+0800 09_Tree[18483:712676] 3
2019-11-30 17:35:57.465494+0800 09_Tree[18483:712676] 4
2019-11-30 17:35:57.465581+0800 09_Tree[18483:712676] 5
2019-11-30 17:35:57.465671+0800 09_Tree[18483:712676] 6
2.3 思路1 - 前序遍历 - 迭代实现
/// 前序遍历- 非递归遍历
- (void)flaten1:(TreeNode *)root {
while (root != nil) {
if (root.left != nil) {
TreeNode *oldRight = root.right; // 先保留右边的节点
root.right = root.left; // 将左子树节点嫁接到右子树上
root.left = nil; // 将左子树清空
// 找出右子树中最右边,最深的节点
TreeNode *rightMost = root;
while (rightMost.right != nil) {
rightMost = rightMost.right;
}
rightMost.right = oldRight; // 将原来右节点嫁接到最右边最深的节点处
}
root = root.right;
}
}
时间复杂度O(n)，空间复杂度O(1)
- 运行结果
2019-11-30 17:48:27.751169+0800 09_Tree[18689:720897] 1
2019-11-30 17:48:27.751369+0800 09_Tree[18689:720897] 2
2019-11-30 17:48:27.751502+0800 09_Tree[18689:720897] 3
2019-11-30 17:48:27.751606+0800 09_Tree[18689:720897] 4
2019-11-30 17:48:27.751697+0800 09_Tree[18689:720897] 5
2019-11-30 17:48:27.751787+0800 09_Tree[18689:720897] 6
三 解题思路 - 后序遍历
image.png
二叉树后序遍历（右 -> 左 -> root）的结果是
6 -> 5 -> 4 -> 3 -> 2 -> 1
，于是可以想到一种新思路。
后序二叉树，每遍历到一个节点，就让它的right指向上一个遍历到的节点，并清空它的left。
image.png
image.png
- 核心代码如下
static TreeNode *prev;
/// 后序遍历 - 递归遍历
- (void)flatten2:(TreeNode *)root {
if (root == nil) {
return;
}
[self flatten2:root.right];
[self flatten2:root.left];
if (prev != nil) {
root.right = prev;
root.left = nil;
}
prev = root;
}
时间复杂度O(n)，空间复杂度O(n)
- 运行结果
2019-11-30 18:15:04.701001+0800 09_Tree[19192:737637] 1
2019-11-30 18:15:04.701164+0800 09_Tree[19192:737637] 2
2019-11-30 18:15:04.701292+0800 09_Tree[19192:737637] 3
2019-11-30 18:15:04.701396+0800 09_Tree[19192:737637] 4
2019-11-30 18:15:04.701493+0800 09_Tree[19192:737637] 5
2019-11-30 18:15:04.701580+0800 09_Tree[19192:737637] 6
本文参考MJ老师的每周一道算法题
