114. Flatten Binary Tree to Linked List

  • 34.1%

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

Given a binary tree, flatten it to a linked list in-place.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
For example,
Given

1
/ \
2 5
/ \ \
3 4 6

The flattened tree should look like:

1
\
2
\
3
\
4
\
5
\
6

Hints:

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


方法一:

题目中要求转换为链表,实际上是Tree,只不过要求左分支都为0,右分支串联。

迭代

对于root, 把root的右节点接上右节点在先序遍历下的前驱节点。然后root右节点指向左节点,左节点设置为空,然后root指向下一个节点。依次迭代。

Share my simple NON-recursive solution, O(1) space complexity!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
void flatten(TreeNode *root) {
TreeNode*now = root;
while (now)
{
if(now->left)
{
//Find current node's prenode that links to current node's right subtree
TreeNode* pre = now->left;
while(pre->right)
{
pre = pre->right;
}
pre->right = now->right;
//Use current node's left subtree to replace its right subtree(original right
//subtree is already linked by current node's prenode
now->right = now->left;
now->left = NULL;
}
now = now->right;
}
}
};

我的代码实现

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

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* 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) {
if(!root || !root->left&&!root->right) return;
TreeNode* curnode = root;
while(curnode){
if(curnode->left){
TreeNode* pre = curnode->left;
while(pre->right)
pre = pre->right;
pre->right = curnode->right;
curnode->right = curnode->left;
curnode->left = NULL;
curnode = curnode->right;
}else{
curnode = curnode->right;
}
}
return;
}
};

我的代码实现:

优化后的代码,相对于上面,优化了if else语句,如果有cur->left,进行一定的处理

无论有没有cur->left,最后都要去cur->right

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* 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) {
if(!root || !root->left&&!root->right) return;
TreeNode* curnode = root;
while(curnode){
if(curnode->left){
TreeNode* pre = curnode->left;
while(pre->right)
pre = pre->right;
pre->right = curnode->right;
curnode->right = curnode->left;
curnode->left = NULL;
}
curnode = curnode->right;
}
return;
}
};

https://discuss.leetcode.com/topic/3995/share-my-simple-non-recursive-solution-o-1-space-complexity

Share my simple NON-recursive solution, O(1) space complexity!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
void flatten(TreeNode *root) {
TreeNode*now = root;
while (now)
{
if(now->left)
{
//Find current node's prenode that links to current node's right subtree
TreeNode* pre = now->left;
while(pre->right)
{
pre = pre->right;
}
pre->right = now->right;
//Use current node's left subtree to replace its right subtree(original right
//subtree is already linked by current node's prenode
now->right = now->left;
now->left = NULL;
}
now = now->right;
}
}
};

https://discuss.leetcode.com/topic/14481/8ms-non-recursive-no-stack-c-solution

8ms, Non-recursive, No stack, C++ solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void flatten(TreeNode *root) {
while (root) {
if (root->left && root->right) {
TreeNode* t = root->left;
while (t->right)
t = t->right;
t->right = root->right;
}

if(root->left)
root->right = root->left;
root->left = NULL;
root = root->right;
}
}

https://discuss.leetcode.com/topic/19087/my-recursive-solution-is-easy-and-clean

My recursive solution is easy and clean!

1
2
3
4
5
6
7
8
9
10
11
void flatten(TreeNode* root) {
if (!root) return;
flatten(root->left);
flatten(root->right);
TreeNode *tmp = root->right;
root->right = root->left;
root->left = nullptr;
while (root->right)
root = root->right;
root->right = tmp;
}

https://discuss.leetcode.com/topic/9933/16-lines-iterative-c-solution

16 lines iterative c++ solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void flatten(TreeNode *root) {
while(root){
if(root->left == NULL)
root = root->right;
else {
if(root->right){
TreeNode *l = root->left;
while(l->right) l = l->right;
l->right = root->right;
}
root->right = root->left;
root->left = NULL;
root = root->right;
}
}
}

Inspired by Morris traversal.


https://discuss.leetcode.com/topic/10606/an-inorder-python-solution

An inorder python solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
# @param root, a tree node
# @return nothing, do it in place
prev = None
def flatten(self, root):
if not root:
return
self.prev = root
self.flatten(root.left)

temp = root.right
root.right, root.left = root.left, None
self.prev.right = temp

self.flatten(temp)



*
/
n
/ \
left right
\
*
*
\
p

The idea is very simple. Suppose n is the current visiting node, and p is the previous node of preorder traversal to n.right.

We just need to do the inorder replacement:

n.left -> NULL

n.right - > n.left

p->right -> n.right


https://discuss.leetcode.com/topic/11444/my-short-post-order-traversal-java-solution-for-share

My short post order traversal Java solution for share

1
2
3
4
5
6
7
8
9
10
11
private TreeNode prev = null;

public void flatten(TreeNode root) {
if (root == null)
return;
flatten(root.right);
flatten(root.left);
root.right = prev;
root.left = null;
prev = root;
}

https://discuss.leetcode.com/topic/9936/straightforward-java-solution

Straightforward Java Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void flatten(TreeNode root) {
if (root == null) return;

TreeNode left = root.left;
TreeNode right = root.right;

root.left = null;

flatten(left);
flatten(right);

root.right = left;
TreeNode cur = root;
while (cur.right != null) cur = cur.right;
cur.right = right;
}

This solution is based on recursion. We simply flatten left and right subtree and paste each sublist to the right child of the root. (don’t forget to set left child to null)


3ms, 4.67%, September 25, 2016

https://discuss.leetcode.com/topic/5783/accepted-simple-java-solution-iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for a binary tree node.
* 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;
Stack<TreeNode> stk = new Stack<TreeNode>();
stk.push(root);
while(!stk.isEmpty()){
TreeNode curr = stk.pop();
if(curr.right!=null)
stk.push(curr.right);
if(curr.left!=null)
stk.push(curr.left);
if(!stk.isEmpty())
curr.right = stk.peek();
curr.left = null;
}
}
}
谢谢你,可爱的朋友。