114. Flatten Binary Tree to Linked List

    /*
     * 114. Flatten Binary Tree to Linked List
     * 2016-5-19 By Mingyang
     * 注意stack不能用！=null来描述，应该用
     * (!stack.isEmpty())来表述！这道题目你会发现好像是根左右的顺序，然后就用stack来写
     * 就是一个preorder的变体，在recursive的方法中呢，我们必须用一个全局变量来保存上一个节点的位置，因为
     * 我们退回来的时候才可以知道lastNode具体的地方。
     */
  

    /*
     * 这个也是根据中规中矩的根左右的顺序，做出来的dfs，下面还利用了
     * stack来做dfs的pre order，原理都是一样的，不过这里利用了
     * 一个全局变量TreeNode来记录上一次的遗留的点，只需要把上次的
     * 右边设为root节点就好了
     */
    public TreeNode pre = null;
    public void flatten(TreeNode root) {
        if (root == null)
            return;
        if (pre != null) {
            pre.right = root;
        }
        pre = root;
        TreeNode left = root.left;
        TreeNode right = root.right;
        flatten(left);
        flatten(right);
        root.left = null;
    }
    /*
     * 这个就是中规中矩的根左右的顺序，由上到下，依次遍历
     * 利用stack完成
     */
    public void flatten1(TreeNode root) {
        if (root == null)
            return;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        TreeNode prev = null;
        while (!stack.isEmpty()) {
            TreeNode temp = stack.pop();
            if (temp.right != null) {
                stack.push(temp.right);
            }
            if (temp.left != null) {
                stack.push(temp.left);
            }
            if (prev != null)
                prev.right = temp;
            temp.left = null;
            prev = temp;
        }
    }

    /*
     * 2016-7-19 by Mingyang
     * 自底向上，右左根的顺序，依次往后退
     * 设置一个prev记录后退的路径
     *大神的自底向上的代码
     */
    private TreeNode prev = null;
    public void flatten(TreeNode root) {
        if (root == null)
            return;
        flatten(root.right);
        flatten(root.left);
        root.right = prev;
        root.left = null;
        prev = root;
    }