Flatten Binary Tree to Linked List:
Given a binary tree, flatten it to a linked list in-place.
For example,
Given1
/ \
2 5
/ \ \
3 4 6The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
这题的主要难点是“in-place”。因为这个flatten的顺序是中、左、右(相当于中序遍历),所以右子树总是在最后的,所以解题思想就是,每次把当前节点的右子树放到左子树的最右边。
图示例:
c++实现代码如下:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> re;
void flatten(TreeNode* root) {
TreeNode *now = root;
while(now){
if(now->left){
TreeNode *pre = now->left;
//找到左子树的最右节点
while(pre->right){
pre = pre->right;
}
//now的右节点放到左子树的最右节点
//now的右节点更新为左节点,左节点赋为NULL
pre->right = now->right;
now->right = now->left;
now->left = NULL;
}
//now不断向右向下
now = now->right;
}
return;
}
};