[Lc]226翻转二叉树

题目

题解

二叉树结构如下：

//Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

1. 递归法

class Solution {//两种方法。1、递归法
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return nullptr;//根节点为空直接返回
        TreeNode *tmp = root->left;//暂存左子树
        root->left = invertTree(root->right);//递归后的右子树赋给左子树
        root->right = invertTree(tmp);//暂存的节点进行递归处理赋给右子树
        return root;//返回根节点
    }
};

2. 队列迭代法

 //这道题可以理解为交换每一个节点的左右子树
class Solution {//两种方法。2.队列迭代法（层次遍历）
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return nullptr;//根节点为空直接返回
        queue<TreeNode*> q{{root}};//建立队列并存储root
        while(!q.empty()){//队列不为空就继续迭代
            TreeNode *cur = q.front();q.pop();//取队首的值
            TreeNode *tmp = cur->left;
            cur->left = cur->right;
            cur->right = tmp;//上面三句就是交换左右子树
            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);//把左右子树压入栈中
        }
        return root;
    }
};