C++刷 LeetCode Hot100 笔记（十）二叉树专题（上）：二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树、二叉树的层序遍历

前面已经刷了数组、哈希、双指针、滑动窗口链表栈和单调栈这一篇开始进二叉树。说实话二叉树这个专题很多人一开始都会有点怕。因为数组、字符串这些东西都是“摆在那儿”的。但树不是它更像一种“递归结构”你不画图的话很容易脑子乱。这一篇先写 5 道二叉树的中序遍历二叉树的最大深度翻转二叉树对称二叉树二叉树的层序遍历这 5 道题特别适合拿来入门因为它们基本把树里最重要的几个东西都碰到了递归DFSBFS左右子树队列层序遍历1. 先把二叉树最基础的东西捋清楚力扣里二叉树节点一般长这样struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} };前期我先只记住三个东西val当前节点值left左孩子right右孩子比如这棵树1 / \ 2 3可以理解成1 是根节点1 的左孩子是 21 的右孩子是 32. 二叉树题我现在最该建立什么感觉我觉得前期最重要的是这两句话2.1 二叉树本质上是递归结构因为一棵树由根节点左子树右子树组成。而左子树、右子树本身又各自是一棵树。所以很多树题天然就适合递归。2.2 做树题时经常要问自己一个问题“如果只看当前这个节点我该做什么”这个问题特别重要。因为递归函数本质上就是先想清楚当前节点怎么处理再把子问题丢给左子树和右子树3. 树的遍历先分清楚树最基础的东西就是遍历。3.1 前序遍历顺序根 - 左 - 右3.2 中序遍历顺序左 - 根 - 右3.3 后序遍历顺序左 - 右 - 根3.4 层序遍历一层一层从上到下遍历一般用队列。3.5 现在怎么记最方便前期就直接记“根”字的位置。前序根最前根 左 右中序根在中间左 根 右后序根最后左 右 根这样记最省事。4. 第一题二叉树的中序遍历4.1 题目大意给你二叉树的根节点root返回它的中序遍历结果。中序顺序是左 - 根 - 右比如1 \ 2 / 3中序遍历结果就是[1,3,2]4.2 这题第一眼该想到什么这题就是最基础的树遍历题。而树遍历最自然的写法就是递归因为先遍历左子树再处理当前节点再遍历右子树这本身就是递归结构。4.3 递归写法class Solution { public: vectorint ans; void inorder(TreeNode* root) { if (root nullptr) return; inorder(root-left); ans.push_back(root-val); inorder(root-right); } vectorint inorderTraversal(TreeNode* root) { inorder(root); return ans; } };4.4 代码怎么理解中序遍历顺序是左 - 根 - 右所以代码里就是inorder(root-left); ans.push_back(root-val); inorder(root-right);你会发现遍历顺序就是代码顺序。这个非常重要。4.5 这题要学到什么这题虽然简单但特别关键因为它会让你建立一个感觉树的递归遍历其实就是递归左子树处理当前节点递归右子树顺序不一样对应的遍历就不一样。4.6 这题最容易犯的错错误 1空节点没处理树题递归一般都要先写if (root nullptr) return;错误 2遍历顺序写错这题是中序不是前序也不是后序。5. 第二题二叉树的最大深度5.1 题目大意给定一个二叉树root返回其最大深度。最大深度的意思就是从根节点到最远叶子节点的最长路径上的节点数。5.2 这题第一眼该想到什么这题特别适合递归。因为一个节点的最大深度其实取决于左子树最大深度右子树最大深度所以当前节点的最大深度就是max(左子树深度, 右子树深度) 1这个思路特别标准。5.3 代码class Solution { public: int maxDepth(TreeNode* root) { if (root nullptr) return 0; int leftDepth maxDepth(root-left); int rightDepth maxDepth(root-right); return max(leftDepth, rightDepth) 1; } };5.4 代码怎么理解假设当前节点是root。那它的最大深度不就是左边这棵子树有多深右边这棵子树有多深取更大的那个再加上当前节点自己这一层所以return max(leftDepth, rightDepth) 1;这个式子你最好记住。5.5 这题你要学到什么这题是特别典型的“树形递归”。树形递归常见思路先问左子树答案再问右子树答案最后合并成当前节点答案这就是很多树题的底层套路。6. 第三题翻转二叉树6.1 题目大意给你一棵二叉树的根节点root翻转这棵二叉树。比如4 / \ 2 7 / \ / \ 1 3 6 9翻转后变成4 / \ 7 2 / \ / \ 9 6 3 1说白了就是每个节点的左右孩子交换6.2 这题第一眼该想到什么这题也很适合递归。因为如果我要翻转一棵树那其实就是把当前节点左右孩子交换再去翻转左子树再去翻转右子树6.3 代码class Solution { public: TreeNode* invertTree(TreeNode* root) { if (root nullptr) return nullptr; swap(root-left, root-right); invertTree(root-left); invertTree(root-right); return root; } };6.4 代码怎么理解当前节点要做的事情特别直接swap(root-left, root-right);然后左右子树自己继续翻转。这题特别适合练“当前节点该做什么”这种思维。6.5 这题学到什么这题表面上像操作题其实本质还是递归。因为“翻转整棵树”可以拆成翻转当前节点翻转左子树翻转右子树这也是二叉树题最常见的拆法之一。7. 第四题对称二叉树7.1 题目大意给你一个二叉树检查它是否轴对称。比如1 / \ 2 2 / \ / \ 3 4 4 3这是对称的。但如果左右结构对应不上那就不是对称。7.2 这题第一眼该想到什么这题一开始很多人会想左子树等不等于右子树但注意这里不是“完全一样”而是镜像对称也就是说要比较的是左边的左子树 对 右边的右子树左边的右子树 对 右边的左子树所以这题最好写成一个函数isMirror(left, right)表示判断两棵树是否互为镜像。7.3 代码class Solution { public: bool isMirror(TreeNode* left, TreeNode* right) { if (left nullptr right nullptr) return true; if (left nullptr || right nullptr) return false; if (left-val ! right-val) return false; return isMirror(left-left, right-right) isMirror(left-right, right-left); } bool isSymmetric(TreeNode* root) { if (root nullptr) return true; return isMirror(root-left, root-right); } };7.4 代码怎么理解两个树要互为镜像必须满足三件事第一点当前两个节点值相等。第二点左边树的左孩子要和右边树的右孩子镜像对应。第三点左边树的右孩子要和右边树的左孩子镜像对应。所以递归式就是isMirror(left-left, right-right) isMirror(left-right, right-left)7.5 这题要学到什么这题特别适合帮我建立一个意识树题里不一定总是“单树递归”有时候也会是双树递归也就是同时递归比较两棵树。这个思维后面还会见到。8. 第五题二叉树的层序遍历8.1 题目大意给你二叉树根节点root返回其节点值的层序遍历。也就是一层一层从左到右访问。比如3 / \ 9 20 / \ 15 7结果是[[3],[9,20],[15,7]]8.2 这题第一眼该想到什么这题和前面几道不一样。前面几道主要是递归 DFS。这题要一层一层来所以最自然想到的是BFS 队列为什么因为队列特别适合“一层一层向外扩”。8.3 整体思路第一步把根节点放进队列。第二步每次先记录当前队列里有多少个节点这个数量就是“当前层的节点数”。第三步把这一层节点依次弹出来同时把它们的左右孩子压进去。这样就能一层一层处理。8.4 代码class Solution { public: vectorvectorint levelOrder(TreeNode* root) { vectorvectorint ans; if (root nullptr) return ans; queueTreeNode* q; q.push(root); while (!q.empty()) { int sz q.size(); vectorint level; for (int i 0; i sz; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left ! nullptr) q.push(node-left); if (node-right ! nullptr) q.push(node-right); } ans.push_back(level); } return ans; } };8.5 代码怎么理解关键点就在这里int sz q.size();这个sz表示当前层有多少个节点。所以这一轮for循环只处理这一层。处理过程中新加入队列的是下一层的节点但不会影响当前层的sz。这就是层序遍历最标准的写法。8.6 这题你要学到什么这题是树的 BFS 入门题。层序遍历固定模型队列先放根节点每轮先记录当前层节点个数再逐个处理这一层同时把下一层压入队列这个模板你后面会反复见到。9. DFS 和 BFS 我现在怎么区分最方便这个很容易混我直接写我自己最实用的区分方式。9.1 DFS深度优先搜索。特点一条路先走到底常用递归也可以用栈树题里很多递归遍历本质上就是 DFS。比如中序遍历最大深度翻转二叉树对称二叉树9.2 BFS广度优先搜索。特点一层一层扩展常用队列树题里最典型的就是层序遍历9.3 我现在先怎么记看到“一层一层”先想queue BFS看到“左子树答案 右子树答案”先想递归 DFS这个区分前期够用了。10. 这五道题放在一起我要看出什么这一篇重点不是只会 5 道题而是要看出来二叉树题也有固定套路10.1 二叉树的中序遍历核心递归遍历左根右顺序10.2 二叉树的最大深度核心左右子树答案取最大树形递归10.3 翻转二叉树核心当前节点交换左右孩子递归处理左右子树10.4 对称二叉树核心双树递归比较镜像位置10.5 二叉树的层序遍历核心BFS队列分层处理11. 二叉树题我现在最该背的几个模板11.1 递归遍历模板void dfs(TreeNode* root) { if (root nullptr) return; dfs(root-left); // 处理当前节点 dfs(root-right); }前序、中序、后序本质上就是“处理当前节点”的位置不同。11.2 树形递归模板int solve(TreeNode* root) { if (root nullptr) return 0; int left solve(root-left); int right solve(root-right); return 根据 left 和 right 算当前答案; }这个模板特别常见。11.3 层序遍历模板queueTreeNode* q; q.push(root); while (!q.empty()) { int sz q.size(); for (int i 0; i sz; i) { TreeNode* node q.front(); q.pop(); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } }这个模板必须熟。12. 这一篇最容易犯的错12.1 空节点判断漏掉树题递归第一句通常都很重要if (root nullptr) ...12.2 遍历顺序混乱特别是前序、中序、后序前期很容易写串。最好的办法就是盯着“根”的位置记。12.3 层序遍历没分层如果不先记int sz q.size();那就不容易把每层分开。12.4 对称二叉树比较错对象这题不是left-left 对 right-left而是left-left 对 right-right left-right 对 right-left这个一定别搞反。13. 这一篇学完我应该达到什么程度这一篇结束后我至少要做到会写中序遍历最大深度翻转二叉树对称二叉树层序遍历会分辨什么是 DFS什么是 BFS什么题适合递归什么题适合队列会建立感觉树题先想当前节点怎么处理再想左右子树怎么办如果做到这一步树的入门其实就算过了。14. 本篇总结这一篇开始正式进入Hot100 二叉树专题。我感觉树题前期最重要的不是一下子做特别难而是先把最核心的感觉养出来树是递归结构DFS 常常就是递归BFS 常常配合队列很多题都可以拆成“当前节点 左子树 右子树”这一篇 5 道题刚好把这些基础块都碰了一遍中序遍历最基础的递归遍历最大深度最典型的树形递归翻转二叉树经典交换操作对称二叉树双树递归层序遍历BFS 入门这几道题吃下来后面再做树题心里就不会那么空了。