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代码如下已通过。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* preOrder(struct TreeNode* root)
{
if(root==NULL||(root->left==NULL&&root->right==NULL))
return root;
struct TreeNode *l=root->left,*r=root->right,*temp;
root->left=NULL;
if(l!=NULL)
{
printf("%d ",l->val);
temp=preOrder(l);
root->right=temp;
while(temp->right!=NULL)
temp=temp->right;
}
else
{
temp=root;
}
temp->right=preOrder(r);
temp->left=NULL;
return root;
}
void flatten(struct TreeNode* root) {
preOrder(root);
}
