首页 > 代码库 > Flatten Binary Tree to Linked List
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
click to show hints.
Hints:
If you notice carefully in the flattened tree, each node‘s right child points to the next node of a pre-order traversal.
C++代码如下：
#include<iostream>#include<new>#include<vector>#include<stack>using namespace std;//Definition for binary treestruct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution{public: void flatten(TreeNode *root) { if(root==NULL) return; vector<TreeNode*> vec; preorder(root,vec); TreeNode *tmp=root; size_t i; for(i=1; i<vec.size(); i++) { //一定要记得将左指针置为NULL tmp->left=NULL; tmp->right=vec[i]; tmp=tmp->right; } tmp->left=tmp->right=NULL; } void preorder(TreeNode *root,vector<TreeNode*> &vec) { stack<TreeNode*> s; while(root||!s.empty()) { while(root) { vec.push_back(root); s.push(root); root=root->left; } if(!s.empty()) { root=s.top(); s.pop(); root=root->right; } } } void createTree(TreeNode *&root) { int i; cin>>i; if(i!=0) { root=new TreeNode(i); if(root==NULL) return; createTree(root->left); createTree(root->right); } }};int main(){ Solution s; TreeNode *root; s.createTree(root); s.flatten(root); while(root) { cout<<root->val<<" "; root=root->right; }}
运行结果：
提交到leetcode时，一直报错，开始不太了解，后来才发现是因为左指针一直没有设为NULL.
class Solution {public: void flatten(TreeNode *root) { if(root==NULL) return; vector<TreeNode*> vec; preorder(root,vec); TreeNode *tmp=root; size_t i; for(i=1; i<vec.size(); i++) { tmp->right=vec[i]; tmp=tmp->right; } tmp->right=NULL; } void preorder(TreeNode *root,vector<TreeNode*> &vec) { stack<TreeNode*> s; while(root||!s.empty()) { while(root) { vec.push_back(root); s.push(root); root=root->left; } if(!s.empty()) { root=s.top(); s.pop(); root=root->right; } } } void createTree(TreeNode *&root) { int i; cin>>i; if(i!=0) { root=new TreeNode(i); if(root==NULL) return; createTree(root->left); createTree(root->right); } }};
注意，最后的指针哪些该设置为空。
Flatten Binary Tree to Linked List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。