HOT100之二叉树翻转二叉树

翻转二叉树

struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x = 0, TreeNode* l = nullptr, TreeNode* r = nullptr) : val(x), left(l), right(r) {} };

这道题其实不难，遍历的部分前面已经说过了，DFS、BFS都可以，所以这道题真正需要想的是：
对于一个节点来说，翻转到底翻转了什么？
仔细看节点定义

TreeNode* left; TreeNode* right;

一个节点里面存了两个指针，分别指向它的左右子树，所以翻转一颗最小二叉树，其实不是交换节点值，而是交换两个指针的指向

swap(root->left, root->right);

欸？这样就结束了吗？
对当前节点来说，确实结束了
但是对整颗树来说，还没有结束，因为当前节点下面的左右子树内部还没有翻转
所以还是那句话：

*每一个节点都当作基于该节点为根节点的一颗独立子树

当前节点要做的事情是：

swap(root->left, root->right);

所以通用到整颗树上就是，遍历加交换

DFS递归法

递归的部分不用重新想复杂了，我们只需要确定两件事：

1. 当前节点要做什么
2. 什么时候停止
   当前节点要做的事情：

swap(root->left, root->right);

停止条件：

if(root == nullptr) return nullptr;

因为当节点为空的时候，说明已经越过叶子节点了，这条路走完，直接返回
于是我们先处理当前节点，再继续处理左右子树

TreeNode* invertTree(TreeNode* root) { if(root == nullptr) return nullptr; swap(root->left, root->right); invertTree(root->left); invertTree(root->right); return root; }

这里有一个容易绕的地方：
我们交换之后再递归，root->left不就是原来的右子树了吗？
是的，但这并不影响
因为我们并不关心它原来在左边还是右边，我们只需要保证当前节点下面的两颗子树都继续翻转即可
当然，也可以先翻转左右子树，最后再交换当前节点

TreeNode* invertTree(TreeNode* root) { if(root == nullptr) return nullptr; invertTree(root->left); invertTree(root->right); swap(root->left, root->right); return root; }

这两种都可以，因为这道题最终只要求每一个节点都交换一次左右子树
不过中序遍历就不要硬套了，因为中间一交换，左右子树的位置发生变化，很容易把同一棵子树处理两次

BFS迭代法

BFS也一样，层序遍历只是负责把每一个节点都拿出来
拿出来之后干什么？
交换它的左右子树

TreeNode* invertTree(TreeNode* root) { if(root == nullptr) return nullptr; queue<TreeNode*> q; q.push(root); while(!q.empty()) { TreeNode* node = q.front(); q.pop(); swap(node->left, node->right); if(node->left) q.push(node->left); if(node->right) q.push(node->right); } return root; }

这里先交换再入队也可以
因为交换只是改变左右位置，并不会让节点消失，左右子树依然都挂在当前节点下面

总结

这道题不要把重点放在“怎么重新连接整颗树”上
二叉树节点本来就用两个指针保存左右子树，所以翻转当前节点只需要：

swap(root->left, root->right);

剩下的事情就是遍历整颗树
DFS也好，BFS也好，本质上都是为了让每一个节点都执行一次交换