題目描述

給你一棵二叉樹的根節點 root ，翻轉這棵二叉樹，并返回其根節點。

題目分析

深度優先搜索（DFS）- 遞歸方式

1. 對于二叉樹的鏡像問題，很容易想到的就是使用遞歸來解決，自底向上依次翻轉每一個節點的左右子節點，即深度優先搜索（DFS）；
2. 需要注意的是在交換節點時，需要一個臨時變量來輔助交換過程。

Code

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (nullptr == root) {return nullptr;}TreeNode* temp = root->left;root->left = invertTree(root->right);root->right = invertTree(temp);return root;}
};

廣度優先搜索（BFS）- 輔助隊列方式

1. 根據題意分析，可以轉換成一個層序遍歷二叉樹的問題，使用隊列的先入先出特性實現，來對每一層的節點進行鏡像，即二叉樹的廣度優先搜索(BFS)；
2. 對于每一層的處理：交換當前層每個節點的左右子節點，并把當前層節點的所有子節點保存到隊列中。循環執行該操作，直至結束。

Code

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (nullptr == root) {return nullptr;}queue<TreeNode*> que_node;que_node.push(root);while (!que_node.empty()) {TreeNode* cur_node = que_node.front();que_node.pop();swap(cur_node->left, cur_node->right);if (nullptr != cur_node->left) {que_node.push(cur_node->left);}if (nullptr != cur_node->right) {que_node.push(cur_node->right);}}return root;}
};