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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public void flatten(TreeNode root) {
if(root == null)
return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode current = stack.pop();
if(current.right != null)
stack.push(current.right);
if(current.left != null)
stack.push(current.left);
if(!stack.isEmpty())
current.right = stack.peek();
current.left = null;
}
}
}Calling stack.pop() or stack.peek() on an empty stack will result in a EmptyStackException. So always make sure you don't call those method on an empty stack. In above implementation when there is only one TreeNode in the stack and we pop it, and the popped TreeNode doesn't have right and left child, so now there will be nothing in the stack, so calling stack.peek() will result in EmptyStackException. So we add the check of, if the stack is not empty, then only we call stack.peek().