Description:

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 分析: 这道题主要要将二叉树拉平。其实如果不要求in-place算法的话，因为这就是一个深搜遍历，pre-ordered traversal. 所以弄个栈存储一下，等下建 很简单就搞定了。但是因为是要求in-place,则需要在递归的过程中，改变树的结构： 基本算法是对任一子树，其左右子树都已经维护好了，即左右子树都是 拉成只有右子树的链了，然后拿到左子树的最右叶子，然后将右子树连接到其右孩子上，这样就维护好了这一子树。

1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     void flatten(TreeNode *root) {13         if(root==NULL) return;14         if(root->left == NULL && root->right == NULL)15             return;16             17         flatten(root->left);18         flatten(root->right);19         TreeNode *nod;20         if(root->left!=NULL)21         {22             nod = root->left;23             while(nod->right!=NULL)24                 nod = nod->right;25             nod->right = root->right;26             root->right = root->left;27             root->left =NULL;28         }29         return;30     }31 };