题目

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

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6

将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

解析

1.使用递归遍历，先将左右子树保存下来，再将左右子树的最后一个节点存下来
2.若有左子树，则将左子树置为空，右子树指向左子树，last指向左子树的最后一个节点
3.若有右子树，若左子树的最后一个节点不为空，则将左子树的右节点指向右节点，last指向右子树的最后一个节点

代码

    public void Flatten(TreeNode root)
    {
        TreeNode last = null;
        PreorderFlatten(root,ref last);
    }

    void PreorderFlatten(TreeNode node,ref TreeNode last)
    {
        if(node == null) return;
        if (node.left == null&&node.right == null)
        {
            last = node;
            return;
        }

        TreeNode left = node.left;//备份左右指针
        TreeNode right = node.right;
        TreeNode leftLast = null;//左右子树最后一个节点
        TreeNode rightLast = null;
        if (left != null)
        {
            PreorderFlatten(left,ref leftLast);//若有左子树，递归将左子树转换为单链表
            node.left = null;//左子树为空
            node.right = left;//右指针改变
            last = leftLast; //将该节点的last保存为左子树
        }

        if (right != null)//若有右子树，递归将右子树转换为单链表
        {
            PreorderFlatten(right, ref rightLast);
            if (leftLast != null)//若找到左子树的最后一个节点（有左子树）
            {
                leftLast.right = right;
            }

            last = rightLast;
        }
    }