The idea is to use a stack to store the right child when we go to left.
Here is the code:
public static void FlattenABinaryTreetoLinkedList(Node root){
Stack<Node> s = new Stack<Node>();
Node c = root;
while(!s.isEmpty()||c!=null){
if(c.left!=null){//keep on going left
if(c.right!=null)//remember the right child
s.push(c.right);
c.right = c.left;
c.left = null;
c = c.right;
}
else{//reach the far left, now we need to go right
Node n = s.pop();
c.right = n;
c = n;
}
}
}
No comments:
Post a Comment