114. 二叉树展开为链表

题意：

解题思路：

思路：
    1
   / \
  2   5
 / \   \
3   4   6
//将 1 的左子树插入到右子树的地方
    1
     \
      2         5
     / \         \
    3   4         6        
//将原来的右子树接到左子树的最右边节点
    1
     \
      2          
     / \          
    3   4  
         \
          5
           \
            6
 //将 2 的左子树插入到右子树的地方
    1
     \
      2          
       \          
        3       4  
                 \
                  5
                   \
                    6   
 //将原来的右子树接到左子树的最右边节点
    1
     \
      2          
       \          
        3      
         \
          4  
           \
            5
             \
              6         
1. 将左子树插入到右子树的地方
2. 将原来的右子树接到左子树的最右边节点
3. 考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null

PHP代码实现：

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    /**
     * @param TreeNode $root
     * @return NULL
     */
    function flatten($root) {
        return $this->flattenBystack($root);
        if ($root == null) return;
        $this->preorder($root, $list);
        $cur = $root;
        for ($i = 1; $i < count($list); $i++) {
            $cur->left = null;
            $cur->right = $list[$i];
            $cur = $cur->right;
        }
    }
    function flattenBystack($root) {
        if ($root == null) return;
        $s = new SplStack;
        $s->push($root);
        $pre = null;
        while (!$s->isEmpty()) {
            $temp = $s->pop();
            if ($pre != null) {
                $pre->right = $temp;
                $pre->left = null;
            }
            if ($temp->right != null) $s->push($temp->right);
            if ($temp->left != null) $s->push($temp->left);
            $pre = $temp;
        }
    }
    function preorder($root, &$list) {
        if ($root == null) return;
        $list[] = $root;
        $this->preorder($root->left, $list);
        $this->preorder($root->right, $list);
    }
}

GO代码实现：

func flatten(root *TreeNode) {
    if root == nil {
        return
    }
    flatten(root.Left)
    flatten(root.Right)
    r := root.Right
    root.Right, root.Left = root.Left, nil
    for root.Right != nil {
        root = root.Right
    }
    root.Right = r
}