【LeetCode Cookbook（C++ 描述）】一刷二叉树综合（上）

本系列文章仅是 GitHub 大神 @halfrost 的刷题笔记 《LeetCode Cookbook》的提纲以及示例、题集的 C++转化。原书请自行下载学习。
本篇文章涉及新手应该优先刷的几道经典二叉树综合算法题。

❗️二叉树解题的思维模式分两类：

1. 是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse() 函数配合外部变量来实现，这叫「遍历」的思维模式。
2. 是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分而治之」的思维模式。

无论使用哪种思维模式，你都需要思考：

如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？我们不需要考虑其他节点，递归函数会在所有节点上执行相同的操作。

LeetCode #226：Invert Binary Tree 翻转二叉树

翻转一棵二叉树，就是将每个节点的左右子节点进行交换，最后的结果就是完全翻转之后的二叉树。

「遍历」

仿照二叉树的递归遍历的代码框架，构造一个 traverse() 方法遍历每个节点，翻转每个节点的左右子节点。因此，对于单个节点，只需要交换自身的子节点即可。

TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;

利用 DFS 递归，层层深入，最终将整棵树的全部节点翻转，核心的针对单个节点的代码放在任意位置均可，这里放在了前序位置；当然，直接将核心代码移到中序位置——不同于前后序位置——是有问题的，交换了左右子树后，左右子树已经换了位置，递归右子树即为递归之前的左子树，因此使用中序位置遍历的顺序应为：递归左子树、交换左右子树、递归左子树。

class Solution {
public:TreeNode* invertTree(TreeNode* root) {//遍历二叉树，交换每个节点的子节点if (root != nullptr) traverse(root);return root;}private:void traverse(TreeNode* root) {if (root != nullptr) {//遍历框架，去遍历左右子树的节点traverse(root->left);// *** 中序位置 ***//每一个节点需要做的事就是交换它的左右子节点TreeNode* temp = root->left;root->left = root->right;root->right = temp;traverse(root->left);  //注意！}}
};

该算法的时间复杂度为$O(n)$ ，空间复杂度为$O(n)$ 。

「分而治之」

我们为 invertTree() 函数赋予定义：将以 root 为根的这棵二叉树翻转，返回翻转后的二叉树的根节点。我们需要考虑的是，对于某一个二叉树节点 root 执行 invertTree(root) 方法，可以利用这一定义实现什么功能？

利用 invertTree(root->left) 方法先把 root 的左子树翻转，再利用 invertTree(root->right) 方法将其右子树翻转，最后将 root 的左右子树交换，即完成整棵二叉树的翻转，这就是分治的思想。

class Solution {
public://定义：将以 root 为根的这棵二叉树翻转，返回翻转后的二叉树的根节点TreeNode* invertTree(TreeNode* root) {if (root == nullptr) return nullptr;//翻转左右子树TreeNode* left = invertTree(root->left);TreeNode* right = invertTree(root->right);//交换左右子节点root->left = right;root->right = left;//和定义逻辑自洽：以 root 为根的这棵二叉树已经被翻转，返回 rootreturn root;}
};

这种「分而治之」的思路，核心在于给递归函数一个合适的定义，然后用函数的定义来解释代码；如果代码逻辑成功自洽，那么说明这一代码所表达的算法是正确的。

广度优先搜索：层序遍历

既然可以通过递归（顺序）遍历来实现，那么也可以通过层序遍历来实现。使用队列存储需要处理的节点，在循环中不断地从队列中取出节点并检查它的左右子节点——如果子节点不为空，我们将其添加到队列中，并在之后交换当前节点的左右子节点。

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root == nullptr) return nullptr;queue<TreeNode*> q;q.push(root);while (!q.empty()) {TreeNode* node = q.front();q.pop();//处理左子树TreeNode* left = node->left;if (left != nullptr) q.push(left);//处理右子树TreeNode* right = node->right;if (right != nullptr) q.push(right);//交换左右子节点node->left = right;node->right = left;}return root;}
};

LeetCode #101：Symmetric Tree 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

实际上，所谓「镜像对称」就是左右子树是否相互翻转，那么只需要左子树的左节点和右子树的右节点、左子树的右节点和右子树的左节点比较即可。

递归法

对于每一层来说，我们比较的都是左子树的左节点和右子树的右节点、左子树的右节点和右子树的左节点是否相等。换言之，我们本质上是在比较两棵树是否对称。因此，由于需要相互进行对比，线性且单一的「遍历」思路就行不通了，我们只能采用「分而治之」的思想。

进一步地，由于我们需要不断地比对 root 的左右子树，引进辅助函数 isMirror(TreeNode* left, TreeNode* right) 来传入两个参数进行递归比对并返回布尔值。

return isMirror(left->left, right->right) && isMirror(left->right, right->left);

显然，我们需要确定终止条件（ base case ）。

首先，节点为空时，分为 3 种情况：

• 左右节点都为空，此时相当于只有一个头节点，是对称的。
• 左节点为空，右节点不为空，显然不对称。
• 左节点不为空，右节点为空，显然也是不对称的。

其次，节点非空时，只需要比较两个节点的值是否相等，相等则对称，反之则不对称。

基本上，整个算法就成形了：

class Solution {
public:bool isSymmetric(TreeNode* root) {if (root == nullptr) return true;return isMirror(root->left, root->right);}private:bool isMirror(TreeNode* left, TreeNode* right) {//如果两个节点都为空，则它们是镜像对称的if (left == nullptr && right == nullptr) return true;//如果只有一个为空，或者节点的值不等，则它们不是镜像对称的if (((left == nullptr) != (right == nullptr)) || left->val != right->val) return false;//递归地检查左子树的左节点和右子树的右节点，以及左子树的右节点和右子树的左节点return isMirror(left->left, right->right) && isMirror(left->right, right->left);}
};

该算法的时间复杂度为$O(n)$ ，空间复杂度为$O(n)$ 。

迭代法

类似于基于广义优先搜索的层序遍历，模拟递归的底层逻辑，构造一个队列，每次将当前层的节点，按照左子树的左节点和右子树的右节点、左子树的右节点和右子树的左节点放入队列，再依次两两出队列，比较数值是否相等。

class Solution {
public:bool isSymmetric(TreeNode* root) {if (root == nullptr) return true;//初始化队列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 == nullptr && right == nullptr) continue;//其中一个节点为空，或者左右节点的值不等，则不对称if (((left == nullptr) != (right == nullptr)) || (left->val != right->val)) return false;//左子树的左节点和右子树的右节点入队列q.push(left->left);q.push(right->right);//左子树的右节点和右子树的左节点入队列q.push(left->right);q.push(right->left);}return true;}
};

LeetCode #100：Same Tree 相同的树

给定两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同，并且节点具有相同的值，则认为他们是相同的。

这道题与上一题 #101 类似，#101 题本质上就是在维护两棵树，只不过这道题是实实在在的两棵树罢了，甚至这道题更为简单，我们无需引入辅助函数。

递归法

我们仍然需要运用「分而治之」的思维模式。只需要判断 p 树的左子树和 q 树的左子树、p 树的右子树和 q 树的右子树是否相等即可。

class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {//判断一对节点是否相同if (p == nullptr && q == nullptr) return true;if (((p == nullptr) != (q == nullptr)) || (p->val != q->val)) return false;//判断其他节点是否相同return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);}
};

假设 p 树有$m$ 个节点，q 树有$n$ 个节点，该算法的时间复杂度和空间复杂度均为$O(min(m,n))$ 。

迭代法

对于每一层来说，只要 p 树和 q 树的对应节点存在且相等即可，类似于层次遍历，使用队列来解决——每次将 p 树和 q 树对应层的节点依次入队列，取出前两个元素弹出队列进行比较，再依次将 p 的左节点和 q 的左节点、p 的右节点和 q 的右节点入队列，……，直至队列为空，遍历结束。

class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {//初始化队列std::queue<TreeNode*> queue;queue.push(p);queue.push(q);while (!queue.empty()) {//从队列中取出两个节点TreeNode* p_Node = queue.front(); queue.pop();TreeNode* q_Node = queue.front(); queue.pop();//若当前为空，则继续循环if (p_Node == nullptr && q_Node == nullptr) continue;//如果其中一个节点为空，另一个不为空，或者值不等，则一定不相同if (((p_Node == nullptr) != (q_Node == nullptr)) || p_Node->val != q_Node->val) return false;// p_Node 节点的左孩子和 q_Node 节点的左孩子入队列queue.push(p_Node->left);queue.push(q_Node->left);// p_Node 节点的右孩子和 q_Node 节点的右孩子入队列queue.push(p_Node->right);queue.push(q_Node->right);}//如果所有节点都匹配，则返回truereturn true;}
};

LeetCode #559：Maximum Depth of N-ary Tree - N 叉树的最大深度

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

先前解决了二叉树的最大深度问题，我们再进一步推广到 N 叉树最大深度问题。

递归法之「分而治之」

首先我们应当找出重复的子问题，即找出单一子树的最大深度，那么对于其他子树也是同样的操作，利用递归逐层实现并比较各子树的最大深度。

for (Node* child : root->children) subTreeMaxDepth = max(subTreeMaxDepth, maxDepth(child));

其次，确定递归终止条件 base case 为 root == nullptr ，递归终止后 N 叉树的最大深度应为 subTreeMaxDepth + 1 。

class Solution {
public:int maxDepth(Node* root) {if (root == nullptr) return 0;int subTreeMaxDepth = 0;for (Node* child : root->children) subTreeMaxDepth = max(subTreeMaxDepth, maxDepth(child));return subTreeMaxDepth + 1;}
};

该算法的时间复杂度为$O(n)$ ，空间复杂度为$O(n)$ 。

递归法之「遍历」

我们很容易从二叉树的遍历框架推广到 N 叉树的情况，只需要更改核心代码对于树的操作即可，traverse() 辅助函数的基本架构不变。

class Solution {
public:int maxDepth(Node* root) {traverse(root);return res;}private://记录递归遍历到的深度int depth = 0;//记录最大的深度int res = 0;void traverse(Node* root) {if (root == nullptr) return;//前序遍历位置depth++;res = max(res, depth);for (Node* child : root->children) traverse(child);//后序遍历位置depth--;}
};

迭代法

我们也可以利用「广度优先搜索」的原理、层序遍历来解决这道题目，使用队列保存每一层的所有节点，把队列里的所有节点弹出队列，然后把这些被弹出的节点各自的子节点入队列。用 depth 维护每一层，此时我们广度优先搜索的队列里存放的是当前层的所有节点。

不同于广度优先搜索的每次只从队列里拿出一个节点，我们需要将队列里的所有节点都拿出来进行拓展，这样能保证我们是一层层地进行拓展的。该 N 叉树的最大深度即为 depth。

class Solution {
public:int maxDepth(Node* root) {//如果根节点为空，则树的深度为0if (root == nullptr) return 0;//使用队列进行层次遍历queue<Node*> q;q.push(root);   //将根节点加入队列int depth = 0;   //初始化深度为 0 //当队列不为空时，继续遍历while (!q.empty()) {//当前层的节点数等于队列的大小int n = q.size();//遍历当前层的所有节点for (int i = 0; i < n; i++) {Node* node = q.front(); // 从队列中取出一个节点q.pop(); // 弹出该节点//遍历当前节点的所有子节点，并将它们加入队列for (Node* child : node->children) {q.push(child); // 将子节点加入队列以便后续处理}}//每处理完一层，深度加 1depth++;}//返回树的最大深度return depth;}
};

LeetCode #111：Minimum Depth of Binary Tree 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到叶子节点的最短路径上的节点数量。

递归法之「分而治之」

每次先遍历左子树，找出左子树的最小深度，再遍历右子树，找出右子树的最小深度，最终再取左子树和右子树最小深度的最小值，加上根节点的高度 1，即 min(leftMindepth, rightMindepth) + 1 为当前二叉树的最小深度；特别地，我们需要注意特殊情况，若节点缺少其中一支（左节点或右节点），这棵由该节点组成的二叉树的最小深度应为 2 而非 1 。

class Solution {
public:int minDepth(TreeNode* root) {// base caseif (root == nullptr) return 0;//递归计算左子树的最小深度int leftDepth = minDepth(root->left);//递归计算右子树的最小深度int rightDepth = minDepth(root->right);//特殊情况处理：如果左子树为空，返回右子树的深度加 1if (leftDepth == 0) return rightDepth + 1;//特殊情况处理：如果右子树为空，返回左子树的深度加 1if (rightDepth == 0) return leftDepth + 1;//以上分两类讨论特殊情况的代码可以合并为// if (leftDepth == 0 || rightDepth == 0) return leftDepth + rightDepth + 1;//计算并返回最小深度：左右子树深度的最小值加 1return min(leftDepth, rightDepth) + 1;}
};

该算法的时间复杂度为$O(n)$ ，空间复杂度为$O(n)$ 。

递归法之「遍历」

递归调用 traverse() 方法回溯遍历整棵二叉树，先做选择，在进入节点时，将 currentDepth 增加 1，再检查叶子节点，如果当前节点是叶子节点（即没有左子节点和右子节点），则将其深度与 minDepthValue 进行比较，并更新 minDepthValue 为两者中的较小值。根据这一流程，递归地遍历左子树和右子树。最后在树的末端撤销选择，离开节点时将 currentDepth 减少 1，以恢复到父节点的深度，确保在遍历其他分支时，currentDepth 能够正确地反映当前节点的深度。

class Solution {
public:int minDepth(TreeNode* root) {if (root == nullptr) return 0;traverse(root);return minDepthValue;}private:int minDepthValue = INT_MAX;int currentDepth = 0;void traverse(TreeNode* root) {if (root == nullptr) return;  // base case//做选择：在进入节点时增加当前深度currentDepth++;//如果当前节点是叶子节点，更新最小深度if (root->left == nullptr && root->right == nullptr) minDepthValue = min(minDepthValue, currentDepth);traverse(root->left);traverse(root->right);//撤销选择：在离开节点时减少当前深度currentDepth--;}
};

迭代法（BFS）

与层序遍历类似，使用队列保存每一层的所有节点，把队列里的所有节点依次弹出队列，当出队列的节点为叶子节点，立即返回当前层数，即为最小深度，否则把这些被弹出的节点各自的子节点（即下一层节点）入队列。用 depth 维护每一层。

class Solution {
public:int minDepth(TreeNode* root) {if (root == nullptr) return 0;queue<TreeNode*> q;q.push(root);// root 本身就是一层，depth 初始化为 1int depth = 1;while (!q.empty()) {int levelSize = q.size();//遍历当前层的节点for (int i = 0; i < levelSize; i++) {TreeNode* cur = q.front();q.pop();//判断是否到达叶子节点if (cur->left == nullptr && cur->right == nullptr) return depth;//将下一层节点加入队列if (cur->left != nullptr) q.push(cur->left);if (cur->right != nullptr) q.push(cur->right);}//增加步数depth++;}return depth;}
};

LeetCode #222：Count Complete Tree Nodes 完全二叉树的节点个数

给你一棵完全二叉树的根节点 root ，求出该树的节点个数。

如果是一棵普通二叉树，完全可以套用遍历框架进行循环累积，时间复杂度为$O(n)$ ：

int countNodes(TreeNode* root) {if (root == nullptr) return 0;return countNodes(root->left) + countNodes(root->right) + 1;
}

如果是一棵满二叉树，节点个数与树的高度¹呈指数关系$n=2^h-1$：

int countNodes(TreeNode* root) {int h = 0;//计算树的深度while (root != nullptr) {root = root->left;h++;}// return pow(2, h) - 1;return (1 << h) - 1;
}

但正如题目所要求的，我们的算法时间复杂度必须低于$O(n)$ ，我们需要进一步优化我们对于完全二叉树的算法。此时，回归概念本质，同时将复杂问题划分为基本可处理的简单问题是非常关键的——所谓「完全二叉树」，其除了最底层以外，其余的每一层节点数都是满的，且最底层的节点全集中在该层最左边的位置，这就很明显地表明，对于一棵完全二叉树，左子树的高度必然大于等于右子树的高度：

• 当左子树的高度等于右子树的高度时，左子树必定是满二叉树。
• 当左子树的高度大于右子树的高度时，右子树必定是满二叉树。

也就是，一棵完全二叉树的两棵子树，至少有一棵是满二叉树。

经过这样的转化，我们就可以将部分子树看作是满二叉树，套用相关的节点公式$n=2^h-1$ 即可得出该子树的节点个数；至于剩余子树，直接递归解决。

class Solution {
public:int countNodes(TreeNode* root) {TreeNode* left = root, *right = root;//沿最左侧和最右侧分别计算高度int leftHeight = 0, rightHeight = 0;while (left != nullptr) {left = left->left;leftHeight++;}while (right != nullptr) {right = right->right;rightHeight++;}//如果左右侧计算的高度相同，则是一棵满二叉树if (leftHeight == rightHeight) return (1 << leftHeight) - 1;//如果左右侧的高度不同，则按照普通二叉树的逻辑计算return 1 + countNodes(root->left) + countNodes(root->right);}
};

由于完全二叉树的性质，其子树一定有一棵是满的，所以一定会触发 leftHeight == rightHeight ，只消耗$O(\log n)$ 的复杂度而不会继续递归。

综上，算法的递归深度就是树的高度$O(\log n)$，每次递归所花费的时间就是 while 循环，需要$O(\log n)$，所以总体的时间复杂度是$O({\log }^{2}n)$；此外，使用了递归，额外调用了栈空间，空间复杂度为$O(\log n)$。

利用二分查找与位运算的解法（LeetCode 官解）

规定根节点位于第 0 层，完全二叉树的最大层数为$h$ 。根据完全二叉树的特性可知，完全二叉树的最左边的节点一定位于最底层，因此从根节点出发，每次访问左子节点，直到遇到叶子节点，该叶子节点即为完全二叉树的最左边的节点，经过的路径长度即为最大层数$h$ 。

当$0\le i<h$ 时，第$i$ 层包含$2^i$ 个节点，最底层包含的节点数最少为 1，最多为$2^h$。

当最底层包含 1 个节点时，完全二叉树的节点个数
$$\sum _{i=0}^{h-1}{2}^i+1=2^0+2^1+2^2+...+2^{h-1}+1=2^h-1+1=2^h$$

当最底层包含$2^h$ 个节点时，完全二叉树的节点个数
$$\sum _{i=0}^h{2}^i=2^{h+1}-1$$

因此对于最大层数为$h$ 的完全二叉树，节点个数一定在$[2^h,2^{h+1}-1]$ 的范围内，我们可以先找到树的最深左子树的高度，在该范围内通过二分查找的方式得到完全二叉树的节点个数的精确解。

具体的做法是，根据节点个数范围的上下界得到当前需要判断的节点个数$k$ ，如果第$k$ 个节点存在，则节点个数一定大于或等于$k$ ，如果第$k$ 个节点不存在，则节点个数一定小于$k$ ，由此可以将查找的范围缩小一半，直到得到节点个数。

为判断$k$ 个节点是否存在，我们定义一个辅助函数 exist() ，如果第$k$ 个节点位于第$h$ 层，则$k$ 的二进制表示包含$h+1$ 位，其中最高位是 1，其余各位从高到低表示从根节点到第 k 个节点的路径，0 表示移动到左子节点，1 表示移动到右子节点。通过位运算得到第$k$ 个节点对应的路径，判断该路径对应的节点是否存在，即可判断第$k$ 个节点是否存在。

class Solution {
public:int countNodes(TreeNode* root) {//如果根节点为空，则树中没有节点if (root == nullptr) return 0;//找到左子树的高度int level = 0;TreeNode* node = root;while (node->left != nullptr) {level++;node = node->left;}//确定节点个数的区间范围int low = 1 << level, high = (1 << (level + 1)) - 1;//使用二分查找确定当前树在第 level 层的实际节点数while (low < high) {//计算中间位置（偏向 high 端，因为实际存在的节点数可能接近 high）int mid = (high - low + 1) / 2 + low;//如果 mid 位置存在节点，则更新 low 为 mid，否则更新 high 为 mid - 1if (exists(root, level, mid)) low = mid;else high = mid - 1;}// 当 low == high 时，找到了最深层实际存在的节点数，即为整棵树的节点总数return low;}//辅助函数，用于判断在第 level 层的第 k 个位置（从 1 开始计数）是否存在节点//利用了二叉树的性质，通过 k 的二进制表示来导航到目标节点bool exists(TreeNode* root, int level, int k) {// bits用于从 k 的二进制表示中逐位提取信息int bits = 1 << (level - 1);TreeNode* node = root;//遍历 k 的每一位（从最高位到最低位）while (node != nullptr && bits > 0) {//如果当前位是 0，则向左子树移动if (!(bits & k)) node = node->left;else node = node->right;    //如果当前位是 1，则向右子树移动//准备检查下一位bits >>= 1;}//如果最终 node 不为空，说明找到了目标节点return node != nullptr;}
};

对于该算法的时间复杂度，首先需要$O(h)$ 的时间得到完全二叉树的最大深度，其中$h$ 是完全二叉树的最大深度（高度）。使用二分查找确定节点个数时，需要查找的次数为$O({\log }^{2}h)=O(h)$，每次查找需要遍历从根节点开始的一条长度为$h$ 的路径，需要$O(h)$ 的时间，因此二分查找的总时间复杂度是$O(h^2)$。

由此，总时间复杂度是$O(h^2)$。由于完全二叉树满足$2^h\le n<2^{h+1}$，因此有 $O(h)=O(\log n)$，$O(h^2)=O({\log }^{2}n)$。

只需要维护有限的额外空间，空间复杂度为$O(1)$。