lintcode | 克隆二叉树

深度复制一个二叉树。

给定一个二叉树，返回一个他的 克隆品 。

样例

给定一个二叉树：

     1   /  /  2    3 / /4   5
返回其相同结构相同数值的克隆二叉树：
     1   /  /  2    3 / /4   5
/** * Definition of TreeNode: * class TreeNode { * public: *     int val; *     TreeNode *left, *right; *     TreeNode(int val) { *         this->val = val; *         this->left = this->right = NULL; *     } * } */class Solution {public:    /**     * @param root: The root of binary tree     * @return root of new tree     */    TreeNode* cloneTree(TreeNode *root) {        // Write your code here        if(root){            TreeNode* T = (TreeNode*)malloc(sizeof(TreeNode));             T->val = root->val;            T->left = cloneTree(root->left);            T->right = cloneTree(root->right);                    return T;        }else{            return NULL;        }    }};
附：
二叉树的表示（摘自lintcode）
对于
  1      1 /   vs   /2          2
这两棵树的BFS序都为 [1,2]. 为了区分他们，我们用 {1, 2, #} 来表示第一棵树，用{1, #, 2} 来表示第二棵树。 其中 # 代表了空节点. 对于 {1,2,#} 我们可以忽略掉末尾的多余空节点，让表示结果更短：{1, 2}.
来一棵大一点的二叉树：
    1   / /  2   3 / /   /4   5   6   / /  7   8
这棵树会被序列化为：{1,2,3,4,5,#,6,#,#,7,8}.