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
思路
利用栈 或者 递归
解题
c++ 栈版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/**
* 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)
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=NULL;
if(!s.empty())
p->right=s.top();
}
}
};
c++ 递归版1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24/**
* 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)
return;
flatten(root->left);
flatten(root->right);
if(NULL==root->left) return;
TreeNode *p=root->left;
while(p->right) p=p->right;
p->right=root->right;
root->right=root->left;
root->left=NULL;
}
};
python 递归版1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return nothing, do it in place
def flatten(self, root):
if not root:
return
self.flatten(root.left)
self.flatten(root.right)
if not root.left:
return
p=root.left
while(p.right):
p=p.right
p.right=root.right
root.right=root.left
root.left=None
