Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
Example
For example, given the following tree:
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
Note
都是在右边,所以先处理右侧
Code
class Solution {
public void flatten(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
if (cur.right != null) {
stack.push(cur.right);
}
if (cur.left != null) {
stack.push(cur.left);
}
if (!stack.isEmpty()) {
cur.right = stack.peek();
}
cur.left = null;
}
}
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;
}
}
Last updated