题目114. 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
1,利用先序遍历
思路:利用先序遍历的顺序,就是线性表的顺序
要特别注意一点,要将节点的左孩子置为空
public class Solution {
public void flatten(TreeNode root) {
if(root == null){
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
TreeNode tail = new TreeNode(1);
TreeNode header = tail;
while(!stack.empty()){
TreeNode node = stack.pop();
if(node.right != null){
stack.push(node.right);
}
if(node.left != null){
stack.push(node.left);
}
tail.right = node;
tail = tail.right;
//重要
tail.left = null;
}
root = header.right;
}
}
