Problem: 114. 二叉树展开为链表
解析
dfs 自顶向下递归
每一次操作都可以视为把当前节点左子树接到右侧，然后把原右子树接到新右子树的最右侧。
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
| class Solution {
public:
void flatten(TreeNode *root) {
dfs(root);
return;
}
void dfs(TreeNode *node) {
if (!node) {
return;
}
if (!node->left) {
dfs(node->right);
return;
}
TreeNode *temp = node->left;
while (temp->right) {
temp = temp->right;
}
temp->right = node->right;
node->right = node->left;
node->left = nullptr;
dfs(node->right);
}
};
|
迭代法
其实就是上个的尾递归优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
void flatten(TreeNode *root) {
TreeNode *node = root;
while (node) {
if (!node->left) {
node = node->right;
continue;
}
TreeNode *temp = node->left;
while (temp->right) {
temp = temp->right;
}
temp->right = node->right;
node->right = node->left;
node->left = nullptr;
node = node->right;
}
return;
}
};
|
