力扣-226-翻转二叉树/剑指Offer-27-二叉树的镜像

直达链接

直观的想法：我可以遍历并重建，但也很明显效率低下，可能达到O(N²)，但或许可能拿来当作练习，检查自己遍历/重建二叉树的基本功
不过现在先想想有没有效率更高的解法，我觉得重点应该是修改节点的两个指针

简单地画图分析后，我认为：

1. 对于有两个孩子节点的节点，只需要将其左右孩子指针互换
2. 对于只有一个孩子节点的节点，可以看作是将它与另一个空节点互换
3. 叶子节点不处理

然后考虑怎么遍历这可树，以及翻转的顺序，这里我们应该自顶向下地处理。可以是层序、也可以先左后右、也可以先右后左
或许也有递归和迭代两种写法

递归

void filp(TreeNode* root) {
	if (!root) return;

	TreeNode* tempNode;
	if (root->left && root->right) {
		filp(root->left);
		filp(root->right);
		tempNode = root->left;
		root->left = root->right;
		root->right = tempNode;
	}
	else if (root->left) {
		filp(root->left);
		root->right = root->left;
		root->left = nullptr;
	}else {
		filp(root->right);
		root->left = root->right;
		root->right = nullptr;
	}
}

// 翻转二叉树
TreeNode* mirrorTree(TreeNode* root) {
	TreeNode* node = root;
	filp(node);
	return root;
}