114. Flatten Binary Tree to Linked List(二叉树转链表)
1.问题描述
Given a binary tree, flatten it to a linked list in-place.
给定一个二叉树,将该二叉树 就地(in-place)转换为单链表。单链表中节点顺序为二叉树前序遍历顺序。
For example, given the following tree:
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
2.C++实现1(基于vector,此方法不是接地转换)
//方法一使用前序遍历,将值存在vector中
class Solution {
public:
void flatten(TreeNode* root) {
vector<TreeNode*> result;
preorder(root, result);
for(int i=1; i<result.size(); i++) {
result[i-1]->left = NULL;
result[i-1]->right = result[i];
}
}
private:
void preorder(TreeNode* node, vector<TreeNode*> &res) {
if(!node)
return;
res.push_back(node);
preorder(node->left, res);
preorder(node->right, res);
}
};
3.C++实现2
//将node指向的节点转为单链表,即将左子树left转为单链表,记录左子树最后一个节点 指针
// left_last,将右子树right转换为单链表,记录右子树最后一个节点指针right_last,
// 最终node 节点与左子树相连,left_last与right相连,函数要将right_last指针传出。
class Solution {
public:
void flatten(TreeNode* root) {
TreeNode* last = NULL;
preorder(root, last);
}
private:
void preorder(TreeNode* node, TreeNode* &last) {
if(!node)
return;
if(!node->left && !node->right) {
last = node;
return;
}
TreeNode* left = node->left;
TreeNode* right = node->right;
TreeNode* left_last = NULL;
TreeNode* right_last = NULL;
if(left) {
preorder(left, left_last);
node->left = NULL;
node->right = left;
last = left_last;
}
if(right) {
preorder(right, right_last);
if(left_last)
left_last->right = right;
last = right_last;
}
}
};
继续阅读
- 我的微信小程序
- 这是我的微信小程序扫一扫
-
- 我的微信公众号
- 我的微信公众号扫一扫
-
评论