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
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 tree struct 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); } } };
注意，最后的指针哪些该设置为空。
