LeetCode| Flatten Binary Tree to Linked List java[将二叉树变成链表]

　　Flatten Binary Tree to Linked List

　　leetcode 原题链接：https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

　　题目如图所示：

　　这算是一道挺有难度的题了，仔细观察树，可以发现，题目是想把一个树，按照preorder traversal的方式全部放到右树去，变成像一个链表一样的树。

　　那么，先看一下preorder traversal递归解法的代码：

　　public void preorderTraversalHelper(TreeNode root, List list) {
　　if(root == null) {
　　return;
　　}
　　list.add(root.val);
　　preorderTraversalHelper(root.left, list);
　　preorderTraversalHelper(root.right, list);
　　}

　　很容易理解，先拿出根，在处理左子树，再处理右子树。

　　那么再看看这个题，能不能也先拿出根，当做flatten以后的根，然后以相同的方式处理左边，将左边的处理结果当做这个跟的右子树，在处理右边，将右边的结果放到前面处理后的右子树。

　　看代码：

　　public class Solution {
　　public void flatten(TreeNode root) {
　　if(root == null){
　　return;
　　}
　　flattenHelper(root);
　　}
　　public TreeNode flattenHelper(TreeNode root){
　　TreeNode left = root.left;
　　TreeNode right = root.right;
　　root.left = null;
　　root.right = null;
　　TreeNode tail = root;
　　if(left != null){
　　tail.right = left;
　　tail = flattenHelper(left);
　　}
　　if(right != null){
　　tail.right = right;
　　tail = flattenHelper(right);
　　}
　　return tail;
　　}
　　}

　　很巧妙的是，在这里，使用了一个tail来记录排好序的的尾巴，若是像常规的写法，直接写

　　root.right = flattenHelper(left);

　　就很难再处理完左子树以后，将右子树的处理结果在后面接上了。