DFS

递归

1. 使用辅助函数 dfs (先序遍历的习惯写法)

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

2. 简化 (不使用辅助函数 dfs)

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

3. 简化 (使用 swap)

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

迭代

class Solution {
public:
    /* DFS preorder */
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> stk;
        if (root) stk.push(root);
        while (!stk.empty()) {
            TreeNode *cur = stk.top();
            stk.pop();
            swap(cur->left, cur->right);
            if (cur->left) stk.push(cur->left);
            if (cur->right) stk.push(cur->right);
        }
        return root;
    }
};

BFS

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