翻转二叉树

题面

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入： root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]

示例 2：

输入： root = [2,1,3] 输出：[2,3,1]

示例 3：

输入： root = [] 输出：[]

提示：

• 树中节点数目范围在 [0, 100] 内
• -100 <= Node.val <= 100

分析

• 显然，题目的要求是将每个节点的左右节点进行交换，可以利用层序遍历的方式来实现

  /**
   * Definition for a binary tree node.
   * struct TreeNode {
   *     int val;
   *     TreeNode *left;
   *     TreeNode *right;
   *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
   *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
   *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
   * right(right) {}
   * };
   */
  class Solution {
  public:
      TreeNode* invertTree(TreeNode* root) {
          if (root == nullptr)
              return nullptr;
          queue<TreeNode*> que;
          que.push(root);
          while (!que.empty()) {
              int size = que.size();
              for (int i = 0; i < size; i++) {
                  TreeNode* cur = que.front();
                  que.pop();
                  TreeNode* left = cur->left;
                  cur->left = cur->right;
                  cur->right = left;
                  if (cur->left != nullptr)
                      que.push(cur->left);
                  if (cur->right != nullptr)
                      que.push(cur->right);
              }
          }
          return root;
      }
  };

• 也可以利用递归的方式来解决，先翻转左子树，再反转右子树，最后反转左右节点

  /**
   * Definition for a binary tree node.
   * struct TreeNode {
   *     int val;
   *     TreeNode *left;
   *     TreeNode *right;
   *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
   *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
   *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
   * right(right) {}
   * };
   */
  class Solution {
  public:
      TreeNode* invertTree(TreeNode* root) {
          if (root == nullptr)
              return nullptr;
          if (root->left)
              invertTree(root->left);
          if (root->right)
              invertTree(root->right);
          TreeNode* left = root->left;
          root->left = root->right;
          root->right = left;
          return root;
      }
  };