跳到主要内容 二叉树算法精讲：翻转、对称、最大与最小深度 | 极客日志
C++ 算法
二叉树算法精讲：翻转、对称、最大与最小深度 本文讲解了二叉树相关的四个经典算法题：翻转二叉树、对称二叉树、二叉树的最大深度及最小深度。通过递归三部曲（确定参数返回值、终止条件、单层逻辑）详细分析了每种情况的处理策略，对比了前序与后序遍历在求深度时的区别，并强调了叶子节点的定义对最小深度的影响。内容涵盖 C++ 实现代码及核心逻辑解析。
本章重点掌握递归法。
226. 翻转二叉树
题目链接：https://leetcode.cn/problems/invert-binary-tree/description/
我们之前介绍的都是各种方式遍历二叉树，这次要翻转了。怎么翻转呢？如果要从整个树来看，翻转真的挺复杂，整个树以中间分割线进行翻转。
可以发现想要翻转它，其实就把每一个节点的左右孩子交换一下就可以了。
关键在于遍历顺序，前中后序应该选哪一种遍历顺序？遍历的过程中去翻转每一个节点的左右孩子 就可以达到整体翻转的效果。
这道题目使用前序遍历和后序遍历 都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转了两次！建议拿纸画一画，就理解了。那么层序遍历可以不可以呢？可以的！只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的！
下面来看一下递归三部曲：
1、确定递归函数的参数和返回值
参数就是要传入节点的指针，不需要其他参数了，通常此时定下来主要参数，如果在写递归的逻辑中发现还需要其他参数的时候，随时补充。
返回值的话其实也不需要，但是题目中给出的要返回 root 节点的指针，可以直接使用题目定义好的函数，所以就函数的返回类型为 TreeNode*。
TreeNode* invertTree (TreeNode* root)
2、确定终止条件
当前节点为空的时候，就返回
if (root == NULL ) return root;
3、确定单层递归的逻辑
因为是前序遍历（后序也可以，左右中），所以先进行交换左右孩子节点，然后反转左子树，反转右子树。
swap (root->left, root->right);
invertTree (root->left);
invertTree (root->right);
完整代码：
class Solution {
public :
TreeNode* invertTree (TreeNode* root) {
if (root == NULL ) return root;
swap (root->left, root->right);
invertTree (root->left);
invertTree (root->right);
微信扫一扫，关注极客日志 微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
Markdown转HTML 将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
HTML转Markdown 将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
return
若要求返回整棵翻转二叉树的遍历结果：
就多了 swap(node->left, node->right); 一行
class Solution {
public :
void invert (TreeNode* node, vector<int >& res) if (node == nullptr ) return ;
res.push_back (node->val);
swap (node->left, node->right);
invert (node->left, res);
invert (node->right, res);
}
vector<int > invertAndTraverse (TreeNode* root) {
vector<int > result;
invert (root, result);
return result;
}
};
101. 对称二叉树 首先想清楚，判断对称二叉树要比较的是哪两个节点，要比较的可不是左右节点！
对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的 ，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。那么如何比较呢？
本题遍历只能是'后序遍历' ，因为我们要不断收集左右孩子的信息，返回给上个节点。才能知道左右两个子树能否相互翻转，所以必须是左右中 的后续遍历顺序。
正因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。
但都可以理解算是后序遍历，尽管已经不是严格上在一个树上进行遍历的后序遍历了。
1、确定递归函数的参数和返回值
因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。返回值自然是 bool 类型。
bool compare (TreeNode* left, TreeNode* right)
2、确定终止条件
要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚 ！否则后面比较数值的时候就会操作空指针了。
节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）
① 左节点为空，右节点不为空，不对称，return false
② 左不为空，右为空，不对称 return false
③ 左右都为空，对称，返回 true
此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：
① 左右都不为空，比较节点数值，不相同就 return false
if (left == NULL && right != NULL ) return false ;
else if (left != NULL && right == NULL ) return false ;
else if (left == NULL && right == NULL ) return true ;
else if (left->val != right->val) return false ;
注意上面最后一种情况，我没有使用 else，而是 else if，因为我们把以上情况都排除之后，剩下的就是左右节点都不为空，且数值相同的情况。
3、确定单层递归的逻辑
此时才进入单层递归的逻辑，单层递归的逻辑就是处理左右节点都不为空，且数值相同的情况，比较两个子树内侧节点和外侧节点是否相等 ：
① 比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
② 比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。
③ 如果左右都对称就返回 true，有一侧不对称就返回 false。
bool outside = compare (left->left, right->right);
bool inside = compare (left->right, right->left);
bool isSame = outside && inside;
return isSame;
如上代码中，我们可以看出使用的遍历方式，左子树左右中，右子树右左中，所以我把这个遍历顺序也称之为'后序遍历'（尽管不是严格的后序遍历）。
class Solution {
public :
bool compare (TreeNode* left, TreeNode* right) if (left == NULL && right != NULL ) return false ;
else if (left != NULL && right == NULL ) return false ;
else if (left == NULL && right == NULL ) return true ;
else if (left->val != right->val) return false ;
bool outside = compare (left->left, right->right);
bool inside = compare (left->right, right->left);
bool isSame = outside && inside;
return isSame;
}
bool isSymmetric (TreeNode* root) if (root == NULL ) return true ;
return compare (root->left, root->right);
}
};
104. 二叉树的最大深度 求高度应该用后序遍历。叶子节点将高度告诉根节点，然后根节点再加 1。求深度应该用前序遍历。
本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。
二叉树节点的深度： 指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从 0 开始还是从 1 开始）
二叉树节点的高度： 指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从 0 开始还是从 1 开始）
而根节点的高度就是二叉树的最大深度 ，所以本题中我们通过后序遍历求得的根节点高度来求二叉树最大深度。
递归三部曲
1、确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为 int 类型。
int getdepth (TreeNode* node)
2、确定终止条件：如果为空节点的话，就返回 0，表示高度为 0。
if (node == NULL ) return 0 ;
3、确定单层递归的逻辑：先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值再 +1 （加 1 是因为算上当前中间节点）就是目前节点为根节点的树的深度。
int leftdepth = getdepth (node->left);
int rightdepth = getdepth (node->right);
int depth = 1 + max (leftdepth, rightdepth);
return depth;
class Solution {
public :
int getdepth (TreeNode* node) if (node == NULL ) return 0 ;
int leftdepth = getdepth (node->left);
int rightdepth = getdepth (node->right);
int depth = 1 + max (leftdepth, rightdepth);
return depth;
}
int maxDepth (TreeNode* root) return getdepth (root);
}
};
调用 getdepth(node->left) 即使 node->left 是 null，它会立即返回 0，但这是 getdepth(node->left) 这个函数调用返回了 0，赋值给 leftdepth。然后，代码继续执行下一行：int rightdepth = getdepth(node->right); 这行仍然会执行。
只看当前节点，不往下递归！
相信子问题已经帮你算好了！
左孩子给我一个结果
右孩子给我一个结果
我把这两个结果在中节点一处理，就是我的答案
相关题目推荐 — 559.n 叉树的最大深度 class Solution {
public :
int maxDepth (Node* root) if (root == 0 ) return 0 ;
int depth = 0 ;
for (int i = 0 ; i < root->children.size (); i++) {
depth = max (depth, maxDepth (root->children[i]));
}
return depth + 1 ;
}
};
111. 二叉树的最小深度 直觉上好像和求最大深度差不多，其实还是差不少的。本题依然是前序遍历和后序遍历都可以，前序求的是深度，后序求的是高度。
本题还有一个误区，在处理节点的过程中，最大深度很容易理解，最小深度就不那么好理解。
这就重新审题了，题目中说的是：最小深度是从根节点到最近叶子节点 的最短路径上的节点数量。注意是叶子节点。
什么是叶子节点，左右孩子都为空的节点才是叶子节点！
递归三部曲：
1、确定递归函数的参数和返回值
参数为要传入的二叉树根节点，返回的是 int 类型的深度。
int getDepth (TreeNode* node)
2、确定终止条件
终止条件也是遇到空节点返回 0，表示当前节点的高度为 0。
if (node == NULL ) return 0 ;
3、确定单层递归的逻辑
需要判断左子树或右子树是否为空！！
如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。最后如果左右子树都不为空，返回左右子树深度最小值 + 1。
求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。
class Solution {
public :
int getDepth (TreeNode* node) if (node == NULL ) return 0 ;
int leftDepth = getDepth (node->left);
int rightDepth = getDepth (node->right);
if (node->left == NULL && node->right != NULL ) {
return 1 + rightDepth;
}
if (node->left != NULL && node->right == NULL ) {
return 1 + leftDepth;
}
int result = 1 + min (leftDepth, rightDepth);
return result;
}
int minDepth (TreeNode* root) return getDepth (root);
}
};
总结 继续学习二叉树，重点掌握递归法，递归三部曲要记牢。
