翻转二叉树

1. LeetCode 226. Invert Binary Tree

2. 描述

给定一颗二叉树，将其翻转

3. 解决方案 1：recursive BFS

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

4. 解决方案 2： BFS

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