【leetcode】Flatten Binary Tree to Linked List

问题是将给定的二叉树变换成令一种形式，这种类型的问题，其模式是，将左子树变换成某种形式，右子树也变换成这种形式，然后再与根结点按规定的方式连接起来，那么整体就变换完成了。这个题我们就可以采用这种形式，麻烦的地方就是在进行连接的时候，我们假设根为root，左子树变换后的根为root_left，右子树变换后的根为 root_right，那么连接的时候应该是root->right = root_left，再连接root_right的时候，应该是root_left所指向的一系列结点的最后一个结点和root_right连接，假设该结点为tail_left，那么就应该是tail_left->right = root_right。这样总体就连接好了。在具体连接的时候，可能要考虑某些结点为NULL的情况。

//

TreeNode *&link(TreeNode *&root){if(root == NULL || root->left == NULL && root->right == NULL) return root;TreeNode *root_left = NULL;TreeNode *root_right = NULL;root_left = link(root->left);root_right = link(root->right);if(root_left != NULL){TreeNode *tail = root_left;//find the last one of root->left.while(tail->right) tail = tail->right;tail->right = root_right;}elseroot_left = root_right;root->right = root_left;root->left = NULL;return root;}void flatten(TreeNode *root) {if(root == NULL) return;root = link(root);}

我们再换个思路，题目中提示我们这种形式其实是树的先根遍历的结果，那么我们回想下基本先根遍历是怎么处理的，我们都是简单的将根结点的val值进行打印。现在如果可以用额外的空间，那么我们就可以将先根遍历中的根结点放到一个顺序容器中，然后将每个结点连起来就是题目要求的了，但是题目的意思很明显不希望这样做，但我们还是希望用这种形式，那怎么办呢？其实我们不难发现，转换后的树形式上就是个单链表，那么问题就转换成单链表的建立。

void preVisit(TreeNode*& pre, TreeNode*root){if(root == NULL)return;TreeNode *right = root->right;TreeNode *left = root->left;root->left = NULL;if(pre == NULL)pre = root;else{pre->right = root;pre = root;}if(left)preVisit(pre, left);if(right)preVisit(pre, right);}

上面的代码就是典型的先根遍历的模板，只是模板中的万能visit函数做了一点稍微复杂的事情。

void flatten(TreeNode* root){if(root = NULL) return;TreeNode *pre = NULL;preVisit(pre, root);}

总结：还是重复前面文章中反复说过的，树的基本遍历的模式一定要熟记于胸，很多衍生的问题都是可以套用模板的。