Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
给一个二叉树，把它展平为链表 in-place
根据展平后的链表的顺序可以看出是先序遍历的结果，所以用inorder traversal。
解法：递归
解法：迭代
Java:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
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;
}
}
Java:
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; // dont forget this!!
}
} Python:
# 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):
return self.flattenRecu(root, None) def flattenRecu(self, root, list_head):
if root != None:
list_head = self.flattenRecu(root.right, list_head)
list_head = self.flattenRecu(root.left, list_head)
root.right = list_head
root.left = None
return root
else:
return list_head
Python:
class Solution:
list_head = None
# @param root, a tree node
# @return nothing, do it in place
def flatten(self, root):
if root != None:
self.flatten(root.right)
self.flatten(root.left)
root.right = self.list_head
root.left = None
self.list_head = root
return root
C++:
// Recursion
class Solution {
public:
void flatten(TreeNode *root) {
if (!root) return;
if (root->left) flatten(root->left);
if (root->right) flatten(root->right);
TreeNode *tmp = root->right;
root->right = root->left;
root->left = NULL;
while (root->right) root = root->right;
root->right = tmp;
}
};
C++:
class Solution {
public:
void flatten(TreeNode* root) {
if (!root) return;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode *t = s.top(); s.pop();
if (t->left) {
TreeNode *r = t->left;
while (r->right) r = r->right;
r->right = t->right;
t->right = t->left;
t->left = NULL;
}
if (t->right) s.push(t->right);
}
}
};