首页 > 代码库 > Leetcode Flatten Binary Tree to Linked List
Leetcode Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1 / 2 5 / \ 3 4 6
The flattened tree should look like:
1 2 3 4 5 6
此题看题目给出的示例就知道是先序遍历
本题用递归求先序遍历
class Solution {public: vector<TreeNode *> res; void preTraverse(TreeNode *root){ if(root == NULL) return; res.push_back(root); preTraverse(root->left); preTraverse(root->right); } void flatten(TreeNode *root) { if(root == NULL) return; preTraverse(root); for(int i = 1 ; i < res.size(); ++ i){ res[i-1]->left =NULL; res[i-1]->right = res[i]; } res[res.size()-1]->left =NULL; res[res.size()-1]->right = NULL; }};
下面用迭代求解，一步步的构造结点，由于题目是先序遍历，可以将右子树链接到左子树最右的孩子结点，如果不明白的可以手动模拟一下看与先序遍历是否相同,然后从根结点一步步往下构造
class Solution {public: void flatten(TreeNode *root) { if(root == NULL) return; while(root){ if(root->left){ TreeNode* ptr = root->left; while(ptr->right) ptr = ptr->right; ptr->right = root->right; root->right = root->left; root->left = NULL; } root = root->right; } }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。