【每日一题】-2019-11-27-114. 二叉树展开为链表

[watchpoints]

给定一个二叉树，原地将它展开为链表。
将一棵二叉树按照前序遍历拆解成为一个 假链表。所谓的假链表是说，用二叉树的 right 指针，来表示链表中的 next 指针

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6
将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[watchpoints]

触类旁通：
Leetcode 1123：最深叶节点的最近公共祖先
Leetcode236：.二叉树的最近公共祖先

[watchpoints]

/**
 * 算法描述
 * 根据例子，你已经发现
 * 1 如果将一个二叉树root转换成一个链表。
 *   （三部曲）
 *  a 只需要将已经转换好的root.left 最后一个元素，指向 已经转换好的root.right 开始节点
 *  b 然后整个左子树 存放到原来右子树位置 
 *  c  root.left =Null

 * 2. 如何root节点知道 获取root.left一个二叉树先序遍历最后一个元素.
 * 3. 转换最小子问题
 *  如果是叶子节点，那就是它了，
 *   如果非叶子节点，优先返回右子树的最后一个位置
 *  也可能是左子树返回值 最后一个位置
 *    1
 *   /  \
 *  2    3    1  2 3
 *
 * time: o(n)
 */
class Solution {
public:
  void flatten(TreeNode *root) {
    if (root == NULL) {
      return;
    }
    dfs(root);
  }

  TreeNode *dfs(TreeNode *pRoot) {
    if (NULL == pRoot) {
      return pRoot; //最基本情况1 
    }

    TreeNode *pLeft = dfs(pRoot->left);   //返回先序遍历最后一个元素
    TreeNode *pRight = dfs(pRoot->right); //返回先序遍历最后一个元素
    if (pLeft != NULL) {
      pLeft->right = pRoot->right; // 1
      pRoot->right = pRoot->left;
      pRoot->left = NULL;
    }
    //最基本情况2
    if (pRight != NULL)
      return pRight;
    if (pLeft != NULL)
      return pLeft; //最基本情况3
    return pRoot;   //最基本情况4
  }
};

规律：返回二叉树中序遍历最有一个元素。

[watchpoints]

同类问题：

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。