題目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,利用先序遍歷
思路:利用先序遍歷的順序,就是線性表的順序
要特別注意一點(diǎn),要將節(jié)點(diǎn)的左孩子置為空
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;
}
}
