递归系列之1:上下翻转二叉树 156 1234二叉树的反转过程

给定一个二叉树，其中所有的右节点要么是具有兄弟节点（拥有相同父节点的左节点）的叶节点，要么为空，将此二叉树上下翻转并将它变成一棵树， 原来的右节点将转换成左叶节点。返回新的根。

输入: [1,2,3,4,5]

1

/ \

2 3

/ \

4 5

输出: 返回二叉树的根 [4,5,2,#,#,3,1]

4

/ \

5 2

/ \

3 1

说明:

对 [4,5,2,#,#,3,1] 感到困惑? 下面详细介绍请查看 二叉树是如何被序列化的。

二叉树的序列化遵循层次遍历规则，当没有节点存在时，'#' 表示路径终止符。

这里有一个例子:

1

/ \

2 3

/

4

\

5

上面的二叉树则被序列化为 [1,2,3,#,#,4,#,#,5].

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/binary-tree-upside-down

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：此题需要注意的是，如果右节点存在，则一定满足：

1. 存在一个同级的左节点

2. 一定是叶子节点

这样才能构成反转的条件

首先需要找到反转后的树根节点，由于是上下反转，根节点就是最左下角的左叶子节点。

首先我们观察root的左子树上下反转后的结果

它从左下角区域变为左上角区域，剩下的两个元素3和1分别变成最右叶节点的左右节点。

看来左子树可以转化为一个子问题，这也提示我们本题可以使用递归方式求解

具体步骤是 ：

1. 首先对root.left（节点2） 上下反转，得到的返回值就是本题答案，记为ans_root（4）

2. 对ans_root.right 持续遍历，直到找到一个ans_root.right 不为NULL，假设为right1（2）

3. 然后将root（1）和root.right（3）（如果存在）分别作为right1的右节点和左节点

4. 需要注意的是：原始的root的左右节点需要置为NULL

TreeNode* upsideDownBinaryTree(TreeNode* root) {
	if (root == NULL || root->left == NULL) {
		return root;
	}
	TreeNode* l = root->left;
	TreeNode* r = root->right;
	TreeNode* tmp = NULL;
	TreeNode* ans = NULL;
	
	root->left = NULL;
	root->right = NULL;
	ans = upsideDownBinaryTree(l);
	tmp = ans;
	
	while(tmp->right != NULL) {
		tmp = tmp->right;
	}
	tmp->left = r;
	tmp->right = root;
	
	return ans;
}

细心的你可能会发现上面的步骤2，即循环查找右叶子节点的步骤是可以省略的，因为

它就是root.left，所以上面的步骤可以简化为：

TreeNode* upsideDownBinaryTree(TreeNode* root) {
	if (root == NULL || root->left == NULL) {
		return root;
	}
	TreeNode* l = root->left;
	TreeNode* r = root->right;
	TreeNode* ans = NULL;
	
	root->left = NULL;
	root->right = NULL;
	ans = upsideDownBinaryTree(l);

	l->left = r;
	l->right = root;
	
	return ans;
}

1. 递归求解的关键是找子问题，如果一个问题存在子问题，那么就可以使用递归的方式解决

2. 递归的核心步骤是假设子问题的答案已知，在此假设基础上求出答案。

比如ans = upsideDownBinaryTree(l)这句话的以上就是假设已经把root.left全部求解了，

那么最终答案就剩下root和root.right的处理，不要纠结upsideDownBinaryTree(l)为什么正确，递归的本质是数学中的数学归纳法，只需要如果这部正确就可以保证下步正确。

3. 递归的结束条件能回到我们一直纠结的问题：upsideDownBinaryTree(l)为什么是对的?

因为这是上面数学归纳法的第一步，如果这第一步正确，就可以保证后面的步骤都正确。

继续用上例把，递归的最末端是下图中的4,这时调用递归upsideDownBinaryTree(2.left)

即upsideDownBinaryTree(4)，根据

if (root == NULL || root->left == NULL) {

return root;

}

知道返回的就是4，然后下次递归5和2，变为4的左右节点，这步是正确。