二叉树展开为链表

题目：

给定一个二叉树，原地将它展开为链表。

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6

将其展开为：

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 {
  private TreeNode pre = null;

  public void flatten(TreeNode root) {
    preOrder(root);
  }
  private void preOrder(TreeNode root) {
    if(root==null) {
      return;
    }
    TreeNode left = root.left;
    TreeNode right = root.right;
    if(pre==null) {
      pre = root;
      pre.left = null;
    }else {
      pre.right = root;
      root.left = null; //重要
      pre = pre.right;
    }
    preOrder(left);
    preOrder(right);
  }
}