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
題目解析：此題為改變二叉樹(shù)的結(jié)構(gòu)膘魄，與單純的先序遍歷還有很大的區(qū)別乌逐。
參考：http://www.cnblogs.com/grandyang/p/4293853.html
http://www.jiuzhang.com/solutions/flatten-binary-tree-to-linked-list/
版本一（從上往下遞歸）:
747807982639154479.jpg
*TreeNode right=root->right;必須加入此句話(huà)，因?yàn)樵谡{(diào)整過(guò)程中改變了root的右孩子创葡，不對(duì)其進(jìn)行保存將丟失浙踢。
//version1
TreeNode *LastNode=NULL;
void flatten(TreeNode *root) {
if(root==NULL)
return;
if(LastNode!=NULL){
LastNode->left=NULL;
LastNode->right=root;
}
LastNode=root;
TreeNode *right=root->right;
flatten(root->left);
flatten(right);
}
版本二（從下往上遞歸）：
2017-01-07_221304.png
void flatten(TreeNode *root) {
if (root == NULL)
return;
flatten1(root->left);
flatten1(root->right);
TreeNode *node = root->right;
root->right = root->left;
root->left = NULL;
while (root->right) root = root->right;
root->right = node;
}
版本三（非遞歸）：
同先序遍歷的非遞歸版本類(lèi)似，加入了連接操作
void flatten(TreeNode *root) {
if (root == NULL)
return;
stack<TreeNode *>stk;
stk.push(root);
TreeNode *node = root;
while (!stk.empty()) {
node = stk.top();
stk.pop();
if (node->right != NULL)
stk.push(node->right);
if (node->left != NULL)
stk.push(node->left);
node->left = NULL;
if (!stk.empty())
node->right = stk.top();
else
node->right = NULL;
}
}
版本四（非遞歸）：從根節(jié)點(diǎn)開(kāi)始灿渴，將根節(jié)點(diǎn)的左子樹(shù)插到根節(jié)點(diǎn)與右子樹(shù)中間洛波。
void flatten(TreeNode *root) {
if (root == NULL)
return;
while (root) {
if (root->left) {
TreeNode *pre = root->left;
while (pre->right)
pre = pre->right;
pre->right = root->right;
root->right = root->left;
root->left = NULL;
}
root = root->right;
}
}
