Flatten Binary Tree to Linked List
Flatten a binary tree to a fake "linked list" in pre-order traversal.
Here we use the right pointer in TreeNode as the next pointer in ListNode.
http://www.lintcode.com/en/problem/flatten-binary-tree-to-linked-list/
Solution 1
假设某节点的左右子树T(root->left)和T(root->right)已经flatten成linked list了：
1
/ \
2 5
\ \
3 6 <- rightTail
\
4 <- leftTail
如何将root、T(root->left)、T(root->right) flatten成一整个linked list？显而易见：
- temp = root->right
- root->right = root->left
- root->left = NULL
- leftTail->right = temp
这里需要用到已经flatten的linked list的尾部元素leftTail, rightTail。所以递归返回值应该是生成的整个linked list的尾部。
//O(n) rum time
//O(h) stack space
class Solution {
public:
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
void flatten(TreeNode *root) {
// write your code here
TreeNode *list_tail = NULL;
list_tail = flattenHelper(root);
}
TreeNode *flattenHelper(TreeNode *root) {
if(root == NULL) return NULL;
TreeNode * leftTail = flattenHelper(root->left);
TreeNode *rightTail = flattenHelper(root->right);
if(root->left) {
TreeNode *tmp = root->right;
root->right = root->left;
root->left = NULL;
leftTail->right = tmp;
}
if(rightTail != NULL) return rightTail;
if(leftTail != NULL ) return leftTail;
return root;
}
};
Solution 2
一个简单的解法，先preorder存下所有node，再构建list，但是这样需要O(n) space + O(logn) sapce for stack.
class Solution {
public:
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
void flatten(TreeNode *root) {
// write your code here
if(root == nullptr) return;
vector<TreeNode*> nodelist;
preorder(root, nodelist);
int n = nodelist.size();
for(int i=0; i<n-1; i++) {
nodelist[i]->right = nodelist[i+1];
nodelist[i]->left = nullptr;
}
nodelist[n-1]->right = nullptr;
nodelist[n-1]->left = nullptr;
}
void preorder(TreeNode *root, vector<TreeNode*> &nodelist) {
if(root == NULL) return;
nodelist.push_back(root);
preorder(root->left, nodelist);
preorder(root->right, nodelist);
}
};
Solution 3
一个牛逼的写法，修改morris traversal，O(1) space。
void flatten(TreeNode *root) {
// write your code here
if(root == nullptr) return;
TreeNode *cur = root;
TreeNode *prev = root;//中序遍历中cur的前置节点
while (cur) {
if(cur->left == NULL) {
//output cur
//for pre-order travesal
cur = cur->right;
} else {
//左孩子不为空，找到它中序遍历的前置节点prev
prev = cur->left;
while (prev->right != NULL && prev->right != cur){
prev = prev->right;
}
if(prev->right == NULL) {
//output cur
//for pre-order travesal
prev->right = cur;
cur = cur->left;
} else { //prev->right == cur, second time access this prev
TreeNode *tmp = cur->right;//这里是关键，其实solution 1
cur->right = cur->left;//里面的LeftTail就是这里的prev
cur->left = NULL;//所以这里还是那样的四步
prev->right = tmp;
cur = tmp;//move to right
}
}
}
}