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
题解
不难看出,要翻转整棵二叉树,就要将其 每一个节点的左右孩子节点都交换 。所以首先想到用递归秒杀:
TreeNode *invertTree(TreeNode *root)
{
if (!root)
return root;
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
进一步考虑用迭代法解决,则迭代顺序应该是“从根节点起,先翻转当前节点的孩子节点,再翻转当前节点的孩子节点的孩子节点,向下类推…”——这其实就是前序遍历的逻辑。因此,可以在前序遍历的 统一迭代法 基础上,将“节点加入结果集”的操作替换成“交换节点的左右孩子节点”即可:
TreeNode *invertTree(TreeNode *root)
{
if (!root)
return root;
stack<TreeNode *> st;
st.push(root);
while (!st.empty())
{
TreeNode *cur = st.top();
st.pop();
if (cur)
{
if (cur->right)
st.push(cur->right); // 右
if (cur->left)
st.push(cur->left); // 左
st.push(cur); // 中
st.push(nullptr); // 空节点标记
}
else
{
swap(st.top()->left, st.top()->right);
st.pop();
}
}
return root;
}
101. 对称二叉树
题目描述
给你一个二叉树的根节点 root
, 检查它是否轴对称。
示例 1:
输入:root = [1,2,2,3,4,4,3]
输出:true
示例 2:
输入:root = [1,2,2,null,3,null,3]
输出:false
提示:
- 树中节点数目在范围
[1, 1000]
内 -100 <= Node.val <= 100
进阶: 你可以运用递归和迭代两种方法解决这个问题吗?
题解
核心是检查“对称”的逻辑:
- 当前节点的左右孩子节点值是否相同
- 当前节点的外层孙子节点值是否相同(左孩子的左孩子 & 右孩子的右孩子)
- 当前节点的内层孙子节点值是否相同(左孩子的右孩子 & 右孩子的左孩子)
- 从根节点向下依此类推
因此容易想到用递归解决,注意左右孩子节点是否为空的分类讨论:
bool compare(TreeNode *left, TreeNode *right)
{
// 首先排除左右有空节点的情况
if (!left ^ !right)
return false; // 一个为空、一个不为空,肯定不对称
else if (!left && !right)
return true; // 皆为空,对称
// 然后处理左右都不为空的情况
if (left->val != right->val)
return false;
bool outCmp = compare(left->left, right->right); // 比较外层情况
bool inCmp = compare(left->right, right->left); // 比较内层情况
return outCmp && inCmp;
}
bool isSymmetric(TreeNode *root)
{
if (!root)
return false;
return compare(root->left, root->right);
}
接下来尝试迭代法解决。判断逻辑和上面相同,由于需要逐层判断,联想到基于层序遍历的框架,利用队列实现:
bool isSymmetric_II(TreeNode *root)
{
if (!root)
return root;
queue<TreeNode *> q;
q.push(root->left);
q.push(root->right);
while (!q.empty())
{
TreeNode *left = q.front();
q.pop();
TreeNode *right = q.front();
q.pop();
// 左右都为空:对称
if (!left && !right)
continue;
// 左右之一为空,或左右不为空但值不相等:不对称
if (!left ^ !right || left->val != right->val)
return false;
// 处理孩子节点
q.push(left->left);
q.push(right->right);
q.push(left->right);
q.push(right->left);
}
return true;
}
注意一下最后孩子节点的入队列顺序,依然是“外层”和“内层”成对入队列的。
104. 二叉树的最大深度
题目描述
给定一个二叉树 root
,返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:3
示例 2:
输入:root = [1,null,2]
输出:2
提示:
- 树中节点的数量在
[0, 104]
区间内。 -100 <= Node.val <= 100
题解
首先考虑递归解决:显然,当前节点的深度 = 左、右孩子节点的深度最大值 + 1。
int maxDepth(TreeNode *root)
{
if (!root)
return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
非常简单。
然后考虑迭代法,由于为了找到最深的一支,不得不遍历整个二叉树,所以联想到利用层序遍历,返回其层数即可。偷个懒,直接搬层序遍历代码调用,不在其内部修改了:
int maxDepth_II(TreeNode *root) {
// 层序遍历,返回层数即可
return levelOrder(root).size();
}
vector<vector<int>> levelOrder(TreeNode *root)
{
vector<vector<int>> res;
queue<TreeNode *> q;
if (!root)
return res;
q.push(root);
while (!q.empty())
{
int size = q.size(); // 注意!先记录当前队长,因为之后会变
vector<int> level; // 当前这一层的节点值
for (int i = 0; i < size; ++i)
{
level.push_back(q.front()->val);
if (q.front()->left)
q.push(q.front()->left);
if (q.front()->right)
q.push(q.front()->right);
q.pop();
}
res.push_back(level);
}
return res;
}
111. 二叉树的最小深度
题目描述
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:2
示例 2:
输入:root = [2,null,3,null,4,null,5,null,6]
输出:5
提示:
- 树中节点数的范围在
[0, 105]
内 -1000 <= Node.val <= 1000
题解
基本思路和 104. 二叉树的最大深度 一样,递归解决需要注意对左右孩子有空节点的情况分类讨论:
int getMin(TreeNode *root) {
if (!root->left && !root->right)
return 1;
else if (root->left && !root->right)
return getMin(root->left) + 1;
else if (!root->left && root->right)
return getMin(root->right) + 1;
else
return min(getMin(root->left), getMin(root->right)) + 1;
}
int minDepth(TreeNode *root)
{
if (!root)
return 0;
return getMin(root);
}
迭代法也是在层序遍历的基础上实现,当发现当前层的某个节点已经是叶子节点时,该层的层数自然就是最小深度了:
int minDepth(TreeNode *root) {
// 层序遍历,期间发现已经遍历到叶子节点就返回当前层数即可
if (!root)
return 0;
queue<TreeNode*> q;
q.push(root);
int depth = 1;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode *cur = q.front();
q.pop();
if (!cur->left && !cur->right)
return depth;
if (cur->left)
q.push(cur->left);
if (cur->right)
q.push(cur->right);
}
depth++;
}
return depth;
}