将普通二叉树转换为完全右倾树

前言：这是扶明发布的第一篇题解
欢迎小伙伴们评论区就坐 ٩(๑òωó๑)۶

读题

题意还是很清晰的大意就是需要把一个普通二叉树转化为右斜树，

                         1
                          \  
    1                      2
   / \                      \
  2   5       ->             3
 / \   \                      \
3   4   6                      4
                                \
                                ...

解题思路

树相关的题一般都有很强的递归规律性，

既然要用递归解决那就需要找到与问题相关的最小单位，

第一步: 将树分解为最小操作单位

//先上简单的 两个叉的家伙

                     2
   2                  \
  / \       ->         3
 3   4                  \
                         4

这个转换起来思路还是很清晰的：先暂存右节点 -> 将左节点换到右边 -> 将原右节点放到现在的右节点的尾部(也就是原左节点的右枝) -> 最后将左枝置为NULL就好了

//再来看一个特殊点的

   2                  2
    \        ->        \
     4                  4

这个转换实际是不需要转换的因为这已经右斜了

//又是一个特殊点的

     2                2
    /        ->        \
   3                    3

其实是一眼能看出了的，但是这个为了统一一下逻辑还是啰嗦一点：先暂存右节点(虽然有节点为NULL) -> 将左节点换到右边 -> 将原右节点放到现在的右节点的尾部 -> 最后将左枝置为NULL

可以发现这个逻辑是和两叉节点的处理逻辑是一样的，这很重要因为可以偷懒了 *( ￣▽￣)

1
2
3

//最后一个

    6    ->    6

尽管这种情况很显然但是还是很重要的，因为它意味着最小的操作单元并不是单个节点 (๑•̀ㅂ•́)و✧

既然是递归地解决那就要从底层向上构造结果，到这里我们已经把最底层的解决了接下来就是从新搭建结果树的过程了

第二步: 将处理好的单元搭建为结果树

很显然结果树的结构是和上面将的操作单元具有非常强的相似性结果

区别在于第一种情况下我们需要找到“左节点”变成了“左枝”，需要找到左枝的尾部

这里就区分了两种思路：一种是用一层循环找到左枝的尾部第二种便是我接下来要讲解的思路啦~

class Solution {
	public:

		TreeNode *tail;

		void flatten(TreeNode *root) {
            //1.防止空树的情况
            //2.处理左右枝为空时直接跳出
			if (!root) return;

            //遇到叶节点先将尾指针更新，然后跳出
			if (!root->left && !root->right) {
				this->tail = root;
				return;
			}

            //将左子树先转换为右倾的
			flatten(root->left);

            //左枝调整到右边
			TreeNode *tmp = root->right;
			if (root->left) {
				root->right = root->left;
				root->left = NULL;
				tail->right = tmp;
			}

            //将原右子树转换为右倾的
			flatten(tmp);
		}
};