HHot 100C++ 图解

226. 翻转二叉树

简单 二叉树 在力扣上做

一句话套路递归交换左右孩子

题目描述

给你一棵二叉树的根节点 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

思路

时间O(n)
空间O(h)

思路

每个结点交换左右孩子,递归下去。前序或后序都行(不像 Q101 需要成对比较)。

图解

1 2 3 4 6 7 9
二叉树(来自本仓库测试数据,nullopt 表示空位)

C++17 题解

src/08_binary_tree.cpp12 行
namespace lc0226 {
class Solution {
 public:
  TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;
    std::swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);
    return root;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q226_invert_tree8 行
lc0226::Solution s;
TreeNode* a = buildTree({4, 2, 7, 1, 3, 6, 9});
TreeNode* inv = s.invertTree(a);
CHECK_EQ(treeToVec(inv), OptVec{4, 7, 2, 9, 6, 3, 1});
freeTree(inv);
TreeNode* b = buildTree({2, 1, 3});
CHECK_EQ(treeToVec(s.invertTree(b)), OptVec{2, 3, 1});
freeTree(b);

↑↓ 选择↵ 打开/ 随时唤起