The problem:

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

A wrong solution :

public class Solution {    public void flatten(TreeNode root) {        if (root == null)            return;            ArrayList
     
       pre = new ArrayList
      
       ();        TreeNode dummy = new TreeNode(0); //use a dummy node for wirtting invariant        pre.add(dummy);        helper(root, pre);    }        private void helper(TreeNode cur, ArrayList
       
         pre) {                if (cur == null)            return;                TreeNode pre_node = pre.get(0);        pre_node.left = null;        pre_node.right = cur;                pre.set(0, cur);        helper(cur.left, pre);//this could change the right child value to cur, before reaching the next nextstatement.        helper(cur.right, pre);    }}
       
      
     

 

An analyssis for the error:

This question could be easily solved by using recursion, but when writing the program, we might introduce a big pitfall.Let's firstly consdiering the following buggy code:    private void helper(TreeNode cur, ArrayList
     
       pre) {                if (cur == null)            return;                TreeNode pre_node = pre.get(0);        pre_node.left = null;        pre_node.right = cur;                pre.set(0, cur);        helper(cur.left, pre);        helper(cur.right, pre);    } The buggy code looks extraordinarily fine, if we thinking it from the perspective of non-recursion program.A big pitfall:1        helper(cur.left, pre); //we call the recursive function2        helper(cur.right, pre);the statement 1 would change the value of cur node.(even it does not change current pointer)in : 1.        pre_node.left = null;2.        pre_node.right = cur;This would lead to a infinite loop, thus result in stack overflow.The classic way to solve this problem is to keep a copy of left child and right child's pointer copy.        TreeNode left = cur.left;        TreeNode right = cur.right;Thus any recursion in the lower level would not affect current level's value.(it's very important!!!)
     

My accepted solution:

public class Solution {    public void flatten(TreeNode root) {        if (root == null)            return;            ArrayList
     
       pre = new ArrayList
      
       ();        TreeNode dummy = new TreeNode(0); //use a dummy node for wirtting invariant        pre.add(dummy);        helper(root, pre);    }        private void helper(TreeNode cur, ArrayList
       
         pre) {                if (cur == null)            return;                TreeNode pre_node = pre.get(0);        pre_node.left = null;        pre_node.right = cur;                TreeNode left = cur.left;        TreeNode right = cur.right;                pre.set(0, cur);        helper(left, pre);        helper(right, pre);    }}