题目描述
Given a binary tree, flatten it to a linked list in-place.
1 /
2 5 / \
3 4 6
The flattened tree should look like:
1
2
3
4
5
6
解题思路
- 参考 这里
/**
* 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:
void flatten(TreeNode* root) {
while(root != NULL){
if(root -> left == NULL){
root = root -> right; // 跳过所有没有左子树的节点
continue;
}
TreeNode* left = root -> left; // 左子树
while(left -> right != NULL){ // 找到左子树的最右节点
left = left -> right;
}
left -> right = root -> right; // 将左子树的最右节点指针 指向 根节点的右子树
root -> right = root -> left; // 重新给根的右子指针赋值，指向当前的left
root -> left = NULL; // 将根节点的左指针赋空
root = root -> right; // 将指针进行移动根的右子节点，进行下次循环
}
}
};
