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递归法递归的部分不用重新想复杂了我们只需要确定两件事当前节点要做什么什么时候停止当前节点要做的事情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; queueTreeNode* 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也好本质上都是为了让每一个节点都执行一次交换