2014
11-19

# LeetCode-Flatten Binary Tree to Linked List[二叉树]

### 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


click to show hints.

Hints:

If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

// LeetCode, Flatten Binary Tree to Linked List
// 递归版1，时间复杂度O(n)，空间复杂度O(logn)
class Solution {
public:
void flatten(TreeNode *root) {
if (root == nullptr) return;  // 终止条件

flatten(root->left);
flatten(root->right);

if (nullptr == root->left) return;

// 三方合并，将左子树所形成的链表插入到root和root->right之间
TreeNode *p = root->left;
while(p->right) p = p->right; //寻找左链表最后一个节点
p->right = root->right;
root->right = root->left;
root->left = nullptr;
}
};


// LeetCode, Flatten Binary Tree to Linked List
// 递归版2
// @author 王顺达(http://weibo.com/u/1234984145)
// 时间复杂度O(n)，空间复杂度O(logn)
class Solution {
public:
void flatten(TreeNode *root) {
flatten(root, NULL);
}
private:
// 把root所代表树变成链表后，tail跟在该链表后面
TreeNode *flatten(TreeNode *root, TreeNode *tail) {
if (NULL == root) return tail;

root->right = flatten(root->left, flatten(root->right, tail));
root->left = NULL;
return root;
}
};


// LeetCode, Flatten Binary Tree to Linked List
// 迭代版，时间复杂度O(n)，空间复杂度O(logn)
class Solution {
public:
void flatten(TreeNode* root) {
if (root == nullptr) return;

stack<TreeNode*> s;
s.push(root);

while (!s.empty()) {
auto p = s.top();
s.pop();

if (p->right)
s.push(p->right);
if (p->left)
s.push(p->left);

p->left = nullptr;
if (!s.empty())
p->right = s.top();
}
}
};


Java代码:

/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/

public class Solution {
public void flatten(TreeNode root) {
if(root == null){
return;
}

if(root.left != null){
TreeNode rightNode = root.right;
TreeNode leftNode = root.left;
root.left = null;
root.right = leftNode;
TreeNode p = leftNode;
while(p.right != null){
p = p.right;
}
p.right = rightNode;
}
flatten(root.right);

}

}

1. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish