leetcode：226. 翻转二叉树

题目

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

示例 1：
[简单] 226. 翻转二叉树 - 图1

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

示例 2：
[简单] 226. 翻转二叉树 - 图2

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

示例 3：

  1. 输入：root = []
  2. 输出：[]

解答 & 代码

解法一：DFS 递归

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     TreeNode* invertTree(TreeNode* root) {
  15.         if(root == nullptr)
  16.             return nullptr;
  18.         // 递归处理左右子树
  19.         TreeNode* inverseLeft = invertTree(root->left);
  20.         TreeNode* inverseRight = invertTree(root->right);
  21.         // 翻转当前节点的左、右节点
  22.         root->left = inverseRight;
  23.         root->right = inverseLeft;
  24.         return root;
  25.     }
  26. };

复杂度分析：设二叉树共 N 个节点

  • 时间复杂度 O(N)：遍历每个节点一次
  • 空间复杂度 O(log N)：栈空间取决于递归深度，即二叉树的高度

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 46.08% 的用户
  4. 内存消耗：9.4 MB, 在所有 C++ 提交中击败了 73.28% 的用户

解法二：BFS

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     TreeNode* invertTree(TreeNode* root) {
  15.         // 一定不能忘了先处理特殊情况！！！！！！！！
  16.         if(root == nullptr)
  17.             return nullptr;
  19.         queue<TreeNode*> nodeQ;
  20.         nodeQ.push(root);
  21.         while(!nodeQ.empty())
  22.         {
  23.             TreeNode* cur = nodeQ.front();
  24.             nodeQ.pop();
  25.             // 将当前节点的左、右节点进行翻转
  26.             TreeNode* tempLeft = cur->left;
  27.             cur->left = cur->right;
  28.             cur->right = tempLeft;
  29.             // 左、右节点入队列
  30.             if(cur->left != nullptr)
  31.                 nodeQ.push(cur->left);
  32.             if(cur->right != nullptr)
  33.                 nodeQ.push(cur->right);
  34.         }
  35.         return root;
  36.     }
  37. };

复杂度分析：设二叉树共 N 个节点

  • 时间复杂度 O(N)：遍历每个节点一次
  • 空间复杂度 O(N)：队列 nodeQ 中存储的节点个数不会超过 N
  1. 执行结果：通过
  3. 执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
  4. 内存消耗：9.5 MB, 在所有 C++ 提交中击败了 42.23% 的用户