## Tuesday, November 11, 2014

### [LeetCode] Flatten Binary Tree to Linked List

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

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: void flatten(TreeNode *root) { if(!root) return; vector allNodes; preorder(root, allNodes); int n = allNodes.size(); for(int i=0; ileft = NULL; allNodes[i]->right = allNodes[i+1]; } allNodes[n-1]->left = allNodes[n-1]->right = NULL; } void preorder(TreeNode *root, vector &allNodes) { if(!root) return; allNodes.push_back(root); preorder(root->left, allNodes); preorder(root->right, allNodes); } };

1
/    \
2     5
\       \
3      6 <- rightTail
\
4  <- leftTail

temp = root->right
root->right  = root->left
root->left = NULL
leftTail->right = temp

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: void flatten(TreeNode *root) { TreeNode* rightTail = flattenBT(root); } TreeNode* flattenBT(TreeNode* root) { if(!root) return NULL; TreeNode *leftTail = flattenBT(root->left); TreeNode *rightTail = flattenBT(root->right); if(root->left) { TreeNode *temp = root->right; root->right = root->left; root->left = NULL; leftTail->right = temp; } if(rightTail) return rightTail; if(leftTail) return leftTail; return root; } };

ln 11：只有当左子树存在时才将它插入右子树中
ln 18-20：返回尾部元素时，需要特殊处理 (1) 有右子树的情况，(2) 无右子树但有左子树的情况，(3)左右子树均不存在的情况。

1. 最后18-20 为何右子树要先被return呢

1. 我感觉是在接的过程中是右子树接在了leftTail的下面，因此如果有右子树的话，最后的tail肯定是rightTail，如果没有右子树但是有左子树，tail肯定是leftTail

2. Absolutely right

2. 只用两个额外的TreeNode指针，非递归，不用栈：
class Solution {
public:
void flatten(TreeNode* root) {
if (root==NULL) return;
TreeNode * cur=root, * prev;
while (cur) {
if (cur->left==NULL) cur=cur->right;
else {
prev=cur->left;
while(prev->right) prev=prev->right;
prev->right=cur->right;
cur->right=cur->left;
cur->left=NULL;
}
}
}
};

3. 请问第二个解法时间复杂度多少呢？

4. good solution! Besides, I think you don't need TreeNode *temp. Do like this:
if (leftTail != null) {
leftTail.right = root.right;
root.right = root.left;
root.left = null;
}

5. 第二种解法为什么要先存好右边，再变右边，再变左边，最后嫁接？
为什么不可以先把右边接到左下方，然后把整个接到root右边，设置root左边为null？
TreeNode left = root.left;
TreeNode right = root.right;
TreeNode cur = left;
5 while (cur.right != null) {
cur = cur.right;
}
cur.right = right;
root.right = left;
root.left = null;
OJ显示第5行null pointer...