@LeetCode二叉树展开为链表--Flatten Binary Tree to Linked List[C++]
问题描述解题思路程序实现
问题描述
给定一个二叉树，原地将它展开为链表。 例如： 将其展开为：
解题思路
观察链表，可以看出是先序遍历二叉树后依次放入链表中。因此，我们明确采用深度优先搜索。
先将根结点放入 vector 中，再遍历左子树直到空结点为止，之后遍历右子树直到空结点为止。不断深搜下去可以将二叉树完全遍历。
之后就是变成链表形式，可以看出链表还是基于二叉树形式形成的，只是将每个结点的左子结点为空，右子结点是先序遍历的结果。
基于以上思路，代码就可以实现。
程序实现
class Solution {
public:
vector
<TreeNode
*> res
;
public:
void flatten(TreeNode
* root
) {
if (!root
) return;
dfs(root
);
int len
= res
.size();
res
[0]->left
= NULL;
for (int i
= 0; i
< len
- 1; i
++) {
res
[i
]->right
= res
[i
+1];
res
[i
+1]->left
= NULL;
}
}
void dfs(TreeNode
* root
) {
if (!root
) return;
else {
res
.push_back(root
);
dfs(root
->left
);
dfs(root
->right
);
}
return;
}
};
@2019.05.26 北京·怀柔
