1、二叉树理论基础

image.png

1.1、二叉树的种类

我们在解题过程中，二叉树有两种主要的形式：满二叉树和完全二叉树。

1.1.1、满二叉树

满二叉树：如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树。
如图所示：
image.png
这棵二叉树为满二叉树，也可以说是深度为k，有 2^k - 1 个节点的二叉树。

1.1.2、完全二叉树

什么是完全二叉树？

完全二叉树的定义如下：在完全二叉树中，除了最底层的节点可能没有填满，其余每层节点数都达到最大值，并且最下面一层的节点都集中在最左边的若干位置。若最底层为第 k 层，则该层包含 1~2^(k - 1) 个节点

大家要看完全二叉树的定义，不要对完全二叉树的判断迷迷瞪瞪。
举个典型的例子：
image.png
之前我们刚刚讲过优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

1.1.3、二叉搜索树

前面介绍的树都是没有数值的，而二叉搜索数是有数值的，二叉搜索树是一棵有序树

  • 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  • 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  • 它的左、右子树也分别为二叉排序树

下面这两棵树都是搜索树
image.png

1.1.4、平衡二叉搜索树

顾名思义，平衡二叉搜索树是在二叉搜索树的基础上平衡了左右子树高度。

平衡二叉搜索树：又被称为 AVL（Adelson-Velsky and Landis）数，且具有以下性质：它是一棵空树或他的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

如图：
image.png
最后一棵不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了1。

C++中map、set、multimap、multiset 的低层实现都是平衡二叉搜索树，所以map、set的增删操作时间复杂度是 logn，注意，unordered_map 和 unordered_set 的低层实现是哈希表，增删操作时间复杂度是 O(1)。

所以大家使用自己熟悉的编程语言写算法，一定要知道常用的容器低层都是如何实现的，最基本的就是map、set等等，否则自己写的代码，自己对其性能分析都分析不清楚！

1.2、二叉树的存储方式

二叉树可以是链式存储，也可以是顺序存储。

那么链式存储方式就用指针， 顺序存储的方式就是用数组。
顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在散落在各个地址的节点串联一起。

链式存储如图：
image.png
链式存储是大家很熟悉的一种方式，那么我们来看看如何顺序存储呢？
其实就是用数组来存储二叉树，顺序存储的方式如图：

image.png

用数组来存储二叉树如何遍历的呢？
如果父节点的数组下标是 i，那么它的左孩子就是 i 2 + 1，右孩子就是 i 2 + 2。
但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。
所以大家要了解，用数组依然可以表示二叉树。

1.3、二叉树的遍历方式

关于二叉树的遍历方式，要知道二叉树遍历的基本方式都有哪些。
一些同学用做了很多二叉树的题目了，可能知道前中后序遍历，可能知道层序遍历，但是却没有框架。
我这里把二叉树的几种遍历方式列出来，大家就可以一一串起来了。

二叉树主要有两种遍历方式：

  1. 深度优先遍历：先往深走，遇到叶子节点再往回走。
  2. 广度优先遍历：一层一层的去遍历。

这两种遍历是图论中最基本的两种遍历方式，后面在介绍图论的时候 还会介绍到。
那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：

  • 深度优先遍历
    • 前序遍历（递归法，迭代法）
    • 中序遍历（递归法，迭代法）
    • 后序遍历（递归法，迭代法）
  • 广度优先遍历
    • 层次遍历（迭代法）

在深度优先遍历中：有三个顺序，前中后序遍历， 有同学总分不清这三个顺序，经常搞混，我这里教大家一个技巧。
这里前中后，其实指的就是中间节点的遍历顺序，只要大家记住 前中后序指的就是中间节点的位置就可以了。
看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式

  • 前序遍历：中左右
  • 中序遍历：左中右
  • 后序遍历：左右中

大家可以对着如下图，看看自己理解的前后中序有没有问题。
image.png
最后再说一说二叉树中深度优先和广度优先遍历实现方式，我们做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。
之前我们讲栈与队列的时候，就说过栈其实就是递归的一种是实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的。
而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。
这里其实我们又了解了栈与队列的一个应用场景了。
具体的实现我们后面都会讲的，这里大家先要清楚这些理论基础。

1.4、二叉树的定义

刚刚我们说过了二叉树有两种存储方式顺序存储，和链式存储，顺序存储就是用数组来存，这个定义没啥可说的，我们来看看链式存储的二叉树节点的定义方式。

  1. struct TreeNode{
  2.     int val;
  3.     TreeNode *left;
  4.     TreeNode *right;
  5.     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  6. };

大家会发现二叉树的定义 和链表是差不多的，相对于链表 ，二叉树的节点里多了一个指针， 有两个指针，指向左右孩子.
这里要提醒大家要注意二叉树节点定义的书写方式。
在现场面试的时候 面试官可能要求手写代码，所以数据结构的定义以及简单逻辑的代码一定要锻炼白纸写出来。
因为我们在刷leetcode的时候，节点的定义默认都定义好了，真到面试的时候，需要自己写节点定义的时候，有时候会一脸懵逼！

2、二叉树的递归遍历

144. 二叉树的前序遍历 - 力扣（LeetCode）
94. 二叉树的中序遍历 - 力扣（LeetCode）
145. 二叉树的后序遍历 - 力扣（LeetCode）

这次我们要好好谈一谈递归，为什么很多同学看递归算法都是“一看就会，一写就废”。

主要是对递归不成体系，没有方法论，每次写递归算法 ，都是靠玄学来写代码，代码能不能编过都靠运气。
本篇将介绍前后中序的递归写法，一些同学可能会感觉很简单，其实不然，我们要通过简单题目把方法论确定下来，有了方法论，后面才能应付复杂的递归。

这里帮助大家确定下来递归算法的三个要素。每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！

  1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
  2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
  3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

好了，我们确认了递归的三要素，接下来就来练练手：
以下以前序遍历为例：

  1. 确定递归函数的参数和返回值：因为要打印出前序遍历节点的数值，所以参数里需要传入vector在放节点的数值，除了这一点就不需要在处理什么数据了也不需要有返回值，所以递归函数返回类型就是void，代码如下：

    1. void traversal(TreeNode* cur, vector<int>& vec)

  2. 确定终止条件：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要要结束了，所以如果当前遍历的这个节点是空，就直接return，代码如下：

    1. if (cur == nullptr) return;

  3. 确定单层递归的逻辑：前序遍历是中左右的循序，所以在单层递归的逻辑，是要先取中节点的数值，代码如下：

    1. vec.push_back(cur->val);    // 中
    2. traversal(cur->left, vec);    // 左
    3. traversal(cur->right, vec);    // 右

    完整代码：

    1. class Solution{
    2. public:
    3.  // 前序遍历
    4.  void traversal(TreeNode* cur, vector<int>& vec){
    5.      if(cur == nullptr) return;
    6.      vec.push_back(cur->val);    // 中
    7.      traversal(cur->left, vec);    // 左
    8.      traversal(cur->right, vec);    // 右
    9.  }
    10.  vector<int> preorderTraversal(TreeNode* root){
    11.      vector<int> vec;
    12.      traversal(root, vec);
    13.      return vec;
    14.  }
    15. };

    中序遍历和后序遍历其实都是大同小异的。

3、二叉树的迭代遍历

看完本篇大家可以使用迭代法，再重新解决如下三道leetcode上的题目：

  • 144.二叉树的前序遍历
  • 94.二叉树的中序遍历
  • 145.二叉树的后序遍历

为什么可以用迭代法（非递归的方式）来实现二叉树的前后中序遍历呢？

我们在栈与队列：匹配问题都是栈的强项(opens new window)中提到了，递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

此时大家应该知道我们用栈也可以是实现二叉树的前后中序遍历了。

3.1、前序遍历（迭代法）

我们先看一下前序遍历。
前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。
为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。
动画如下：
二叉树（上） - 图9
不难写出如下代码：（注意空节点不入栈）

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     // 迭代法实现前序遍历
  15.     // 递归法：中左右
  16.     // 迭代法：入栈顺序：右左中
  17.     vector<int> preorderTraversal(TreeNode* root) {
  18.         stack<TreeNode*> stk;
  19.         vector<int> result;
  20.         if(root == nullptr){
  21.             return result;
  22.         }
  23.         stk.push(root);     // 先将根节点入栈
  24.         while(!stk.empty()){
  25.             TreeNode* node = stk.top();     // 中
  26.             result.push_back(node->val);
  27.             stk.pop();
  28.             if(node->right){                // 右(空节点不入栈)
  29.                 stk.push(node->right);
  30.             }
  31.             if(node->left){                 // 左(空节点不入栈)
  32.                 stk.push(node->left);
  33.             }
  34.         }
  35.         return result;
  36.     }
  37. };

此时会发现貌似使用迭代法写出前序遍历并不难，确实不难。
此时是不是想改一点前序遍历代码顺序就把中序遍历搞出来了？
其实还真不行！
但接下来，再用迭代法写中序遍历的时候，会发现套路又不一样了，目前的前序遍历的逻辑无法直接应用到中序遍历上。

3.2、中序遍历（迭代法）

为了解释清楚，我说明一下 刚刚在迭代的过程中，其实我们有两个操作：

  1. 处理：将元素放进result数组中
  2. 访问：遍历节点

分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。
那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。
那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。
动画如下：
二叉树（上） - 图10
中序遍历C++代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<int> inorderTraversal(TreeNode* root) {
  15.         stack<TreeNode*> stk;
  16.         vector<int> result;
  17.         TreeNode* cur = root;
  18.         while(cur || !stk.empty()){
  19.             if(cur != nullptr){   // 用指针来访问节点，访问到最底层
  20.                 stk.push(cur);    // 将访问过的节点放入栈中
  21.                 cur = cur->left;
  22.             }
  23.             else{
  24.                 cur = stk.top();        // 从栈里弹出的数据，就是要处理的数据
  25.                 stk.pop();
  26.                 result.push_back(cur->val);
  27.                 cur = cur->right;
  28.             }
  29.         }
  30.         return result;
  31.     }
  32. };

3.3、后序遍历（迭代法）

再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：
image.png
所以后序遍历只需要前序遍历的代码稍作修改就可以了，代码如下：

  1. class Solution{
  2. public:
  3.     vector<int> postorderTraversal(TreeNode* root){
  4.         vector<int> result;
  5.         stack<TreeNode*> st;
  6.         st.push(root);
  7.         while(!st.empty()){
  8.             TreeNode* cur = st.top();            // 中
  9.             result.push_back(cur->val);
  10.             st.pop();
  11.             if(cur->left) st.push(cur->left);    // 左
  12.             if(cur->right) st.push(cur->right);    // 右
  13.         }
  14.         reverse(result.begin(), result.end());    // 中右左 --> 左右中
  15.         return result;
  16.     }
  17. };

4、二叉树的统一迭代法

此时我们在二叉树：一入递归深似海，从此offer是路人(opens new window)中用递归的方式，实现了二叉树前中后序的遍历。
在二叉树：听说递归能做的，栈也能做！(opens new window)中用栈实现了二叉树前后中序的迭代遍历（非递归）。

之后我们发现迭代法实现的先中后序，其实风格也不是那么统一，除了先序和后序，有关联，中序完全就是另一个风格了，一会用栈遍历，一会又用指针来遍历。
实践过的同学，也会发现使用迭代法实现先中后序遍历，很难写出统一的代码，不像是递归法，实现了其中的一种遍历方式，其他两种只要稍稍改一下节点顺序就可以了。

其实针对三种遍历方式，使用迭代法是可以写出统一风格的代码！
重头戏来了，接下来介绍一下统一写法。

我们以中序遍历为例，在二叉树：听说递归能做的，栈也能做！(opens new window)中提到说使用栈的话，无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。
那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。
如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。

二叉树前序遍历、中序遍历、后序遍历的统一风格的代码

前序遍历

  1. class Solution{
  2. public:
  3.     vector<int> postorderTraversal(TreeNode* root){
  4.         stack<TreeNode*> st;
  5.         vector<int> result;
  6.         if(root == NULL) return result;
  7.         st.push(root);        // 根节点先入栈
  8.         while(!st.empty()){
  9.             TreeNode* node = st.top();
  10.             if(node != NULL){    // 如果节点非空，表明当前节点不是我们设置标志的节点，我们需要继续判断当前节点是否有左右孩子
  11.                 st.pop();        // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
  12.                 if(node->right) st.push(node->right);    // 右(空节点不入栈)
  13.                 if(node->left) st.push(node->left);        // 左(空节点不入栈)
  14.                 st.push(node);                            // 中
  15.                 st.push(NULL);    // 给当前节点设置标志
  16.             }
  17.             else{
  18.                 st.pop();        // 弹出空指针(即我们设置的标志)
  19.                 result.push_back(st.top());        // 这是我们想要操作的节点
  20.                 st.pop();
  21.             }
  22.         }
  23.         return result;
  24.     }
  25. };

中序遍历

  1. class Solution{
  2. public:
  3.     vector<int> postorderTraversal(TreeNode* root){
  4.         stack<TreeNode*> st;
  5.         vector<int> result;
  6.         if(root == NULL) return result;
  7.         st.push(root);        // 根节点先入栈
  8.         while(!st.empty()){
  9.             TreeNode* node = st.top();
  10.             if(node != NULL){    // 如果节点非空，表明当前节点不是我们设置标志的节点，我们需要继续判断当前节点是否有左右孩子
  11.                 st.pop();        // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
  12.                 if(node->right) st.push(node->right);    // 右(空节点不入栈)
  13.                 st.push(node);                            // 中
  14.                 st.push(NULL);    // 给当前节点设置标志
  15.                 if(node->left) st.push(node->left);        // 左(空节点不入栈)
  16.             }
  17.             else{
  18.                 st.pop();        // 弹出空指针(即我们设置的标志)
  19.                 result.push_back(st.top());        // 这是我们想要操作的节点
  20.                 st.pop();
  21.             }
  22.         }
  23.         return result;
  24.     }
  25. };

后序遍历

  1. class Solution{
  2. public:
  3.     vector<int> postorderTraversal(TreeNode* root){
  4.         stack<TreeNode*> st;
  5.         vector<int> result;
  6.         if(root == NULL) return result;
  7.         st.push(root);        // 根节点先入栈
  8.         while(!st.empty()){
  9.             TreeNode* node = st.top();
  10.             if(node != NULL){    // 如果节点非空，表明当前节点不是我们设置标志的节点，我们需要继续判断当前节点是否有左右孩子
  11.                 st.pop();        // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
  12.                 st.push(node);                            // 中
  13.                 st.push(NULL);    // 给当前节点设置标志
  14.                 if(node->right) st.push(node->right);    // 右(空节点不入栈)
  15.                 if(node->left) st.push(node->left);        // 左(空节点不入栈)
  16.             }
  17.             else{
  18.                 st.pop();        // 弹出空指针(即我们设置的标志)
  19.                 result.push_back(st.top());        // 这是我们想要操作的节点
  20.                 st.pop();
  21.             }
  22.         }
  23.         return result;
  24.     }
  25. };

此时我们写出了统一风格的迭代法，不用在纠结于前序写出来了，中序写不出来的情况了。
但是统一风格的迭代法并不好理解，而且想在面试直接写出来还有难度的。
所以大家根据自己的个人喜好，对于二叉树的前中后序遍历，选择一种自己容易理解的递归和迭代法。

5、二叉树的层序遍历

层序遍历一个二叉树，就收从左到右一层一层的去遍历二叉树。这种遍历方式和我们之前将的都不太一样。

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

使用队列实现二叉树广度优先遍历，动画如下：
二叉树（上） - 图12
这样就实现了层序从左到右遍历二叉树。

5.1、二叉树的层序遍历

102. 二叉树的层序遍历 - 力扣（LeetCode）

我们用层序遍历的方法，实现了二叉树的广度搜索问题。C++代码如下：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<vector<int>> levelOrder(TreeNode* root) {
  15.         vector<vector<int>> result;
  16.         queue<TreeNode*> que;
  17.         if(root == NULL) return result;
  18.         que.push(root);
  19.         while(!que.empty()){
  20.             vector<int> temp;           // 用一个临时的一维数组来存二叉树中一层的节点
  21.             int size = que.size();      // 队列的大小,即二叉树当前这一层的节点数
  22.             while(size--){              // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
  23.                 TreeNode* cur = que.front();
  24.                 temp.push_back(cur->val);
  25.                 que.pop();
  26.                 if(cur->left) que.push(cur->left);      // 左节点非空就入队
  27.                 if(cur->right) que.push(cur->right);    // 右节点非空就入队
  28.             }
  29.             result.push_back(temp);
  30.         }
  31.         return result;
  32.     }
  33. };

5.2、二叉树的层序遍历 II

107. 二叉树的层序遍历 II - 力扣（LeetCode）

这道题的思路很简单，就是先按照顺序自上而下的层序遍历二叉树，然后在最后面要输出结构的时候，我们反转一下二维数组的顺序就行了。

C++代码如下：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     // 先按顺序自上向下的层序遍历，然后在最后面要输出的时候反转一下数组即可
  15.     vector<vector<int>> levelOrderBottom(TreeNode* root) {
  16.         vector<vector<int>> result;
  17.         queue<TreeNode*> que;
  18.         if(root == nullptr) return result;
  19.         que.push(root);
  20.         while(!que.empty()){
  21.             int size = que.size();
  22.             vector<int> temp;
  23.             while(size--){
  24.                 TreeNode* cur = que.front();
  25.                 temp.push_back(cur->val);
  26.                 que.pop();
  27.                 if(cur->left) que.push(cur->left);
  28.                 if(cur->right) que.push(cur->right);
  29.             }
  30.             result.push_back(temp);
  31.         }
  32.         reverse(result.begin(), result.end());      // 在这里反转以下数组即可
  33.         return result;
  34.     }
  35. };

5.3、二叉树的右视图

199. 二叉树的右视图 - 力扣（LeetCode）

思路：
层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组，随后返回result就可以了。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<int> rightSideView(TreeNode* root) {
  15.         vector<int> result;
  16.         queue<TreeNode*> que;
  17.         if(root == nullptr) return result;
  18.         que.push(root);
  19.         // result.push_back(root->val);    // 根节点只有一个，肯定能被右侧看到
  20.         while(!que.empty()){
  21.             int size = que.size();      // 当前这一层的节点数
  22.             while(size){
  23.                 TreeNode* cur = que.front();
  24.                 que.pop();
  25.                 if(cur->left) que.push(cur->left);
  26.                 if(cur->right) que.push(cur->right);
  28.                 if(size == 1){          // 如果size为1，说明当前访问的节点是这一层的最后一个节点
  29.                     result.push_back(cur->val);
  30.                 }
  31.                 size--;
  32.             }
  33.         }
  34.         return result;
  35.     }
  36. };

5.4、二叉树的层平均值

637. 二叉树的层平均值 - 力扣（LeetCode）

本题就是层序遍历的时候，把单层求个总和再取一个均值。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<double> averageOfLevels(TreeNode* root) {
  15.         queue<TreeNode*> que;
  16.         if (root != NULL) que.push(root);
  17.         vector<double> result;
  18.         while (!que.empty()) {
  19.             int size = que.size();
  20.             double sum = 0; // 统计每一层的和
  21.             for (int i = 0; i < size; i++) {
  22.                 TreeNode* node = que.front();
  23.                 que.pop();
  24.                 sum += node->val;
  25.                 if (node->left) que.push(node->left);
  26.                 if (node->right) que.push(node->right);
  27.             }
  28.             result.push_back(sum / size); // 将每一层均值放进结果集
  29.         }
  30.         return result;
  31.     }
  32. };

5.5、N 叉树的层序遍历

429. N叉树的层序遍历

思路：
这道题依旧是模板提题，只不过是一个节点有多个孩子了，需要注意一下N叉树的定义方式。

C++代码：

  1. /*
  2. // Definition for a Node.
  3. class Node {
  4. public:
  5.     int val;
  6.     vector<Node*> children;
  8.     Node() {}
  10.     Node(int _val) {
  11.         val = _val;
  12.     }
  14.     Node(int _val, vector<Node*> _children) {
  15.         val = _val;
  16.         children = _children;
  17.     }
  18. };
  19. */
  21. class Solution {
  22. public:
  23.     vector<vector<int>> levelOrder(Node* root) {
  24.         vector<vector<int>> result;
  25.         queue<Node*> que;
  26.         if(root != NULL) que.push(root);
  27.         while(!que.empty()){
  28.             int size = que.size();
  29.             vector<int> temp;
  30.             for(int i = 0; i < size; i++){
  31.                 Node* cur = que.front();
  32.                 temp.push_back(cur->val);       // 就算N叉树的每组子节点都用null来分隔，我们在后面节点入队的时候也有判断
  33.                 que.pop();
  34.                 for(int j = 0; j < cur->children.size(); j++){
  35.                     if(cur->children[j]){       // 在这里判断
  36.                         que.push(cur->children[j]);
  37.                     }
  38.                 }
  39.             }
  40.             result.push_back(temp);
  41.         }
  42.         return result;
  43.     }
  44. };

5.6、在每个树行中找最大值

515. 在每个树行中找到最大值 - 力扣（LeetCode）

思路：
还是层序遍历，取每一层的最大值就行了，依旧是套模板

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<int> largestValues(TreeNode* root) {
  15.         vector<int> result;
  16.         queue<TreeNode*> que;
  17.         if(root == nullptr) return result;
  18.         que.push(root);
  19.         while(!que.empty()){
  20.             int size = que.size();
  21.             int max = INT_MIN;            // 初始化为最小值
  22.             for(int i = 0; i < size; i++){
  23.                 TreeNode* cur = que.front();
  24.                 if(cur->val > max){
  25.                     max = cur->val;
  26.                 }
  27.                 que.pop();
  28.                 if(cur->left) que.push(cur->left);
  29.                 if(cur->right) que.push(cur->right);
  30.             }
  31.             result.push_back(max);
  32.         }
  33.         return result;
  34.     }
  35. };

5.7、填充每个节点的下一个右侧节点指针

116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）

思路：
本题依旧是层序遍历，只不过在单层遍历的时候，让左边的节点指向右边的节点，然后让单层中最后一个节点指向NULL就行了。

  1. /*
  2. // Definition for a Node.
  3. class Node {
  4. public:
  5.     int val;
  6.     Node* left;
  7.     Node* right;
  8.     Node* next;
  10.     Node() : val(0), left(NULL), right(NULL), next(NULL) {}
  12.     Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
  14.     Node(int _val, Node* _left, Node* _right, Node* _next)
  15.         : val(_val), left(_left), right(_right), next(_next) {}
  16. };
  17. */
  19. class Solution {
  20. public:
  21.     Node* connect(Node* root) {
  22.         queue<Node*> que;
  23.         if(root == NULL) return root;
  24.         que.push(root);
  25.         while(!que.empty()){
  26.             int size = que.size();
  27.             for(int i = 0; i < size; i++){
  28.                 Node* cur = que.front();
  29.                 que.pop();
  30.                 if(cur->left) que.push(cur->left);
  31.                 if(cur->right) que.push(cur->right);
  32.                 cur->next = que.front();    // 左孩子指向右孩子
  33.                 if(i == size - 1){          // 如果当前节点是单层中最后一个节点，那我们让它指向NULL
  34.                     cur->next = NULL;
  35.                 }
  36.             }
  37.         }
  38.         return root;
  39.     }
  40. };

5.8、填充每个节点的下一个右侧节点 II

117. 填充每个节点的下一个右侧节点指针 II

思路：
跟那道题的不同之处，是上面这道题题目说的是一棵完全二叉树，这道题没有这么要求。但其实思路是一样的，一样的代码迁移过来。

  1. /*
  2. // Definition for a Node.
  3. class Node {
  4. public:
  5.     int val;
  6.     Node* left;
  7.     Node* right;
  8.     Node* next;
  10.     Node() : val(0), left(NULL), right(NULL), next(NULL) {}
  12.     Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
  14.     Node(int _val, Node* _left, Node* _right, Node* _next)
  15.         : val(_val), left(_left), right(_right), next(_next) {}
  16. };
  17. */
  19. class Solution {
  20. public:
  21.     Node* connect(Node* root) {
  22.         queue<Node*> que;
  23.         if(root == NULL) return root;
  24.         que.push(root);
  25.         while(!que.empty()){
  26.             int size = que.size();
  27.             for(int i = 0; i < size; i++){
  28.                 Node* cur = que.front();
  29.                 que.pop();
  30.                 if(cur->left) que.push(cur->left);
  31.                 if(cur->right) que.push(cur->right);
  32.                 cur->next = que.front();    // 左边的节点指向它右边的节点
  33.                 if(i == size - 1){          // 如果当前节点是单层中最后一个节点，那么让它指向NULL
  34.                     cur->next = NULL;
  35.                 }
  36.             }
  37.         }
  38.         return root;
  39.     }
  40. };

5.9、二叉树的最大深度

104. 二叉树的最大深度

思路：
如果使用迭代法的话，使用二叉树的层序遍历是最合适的，因为二叉树的层数就是它的深度，因为我们至少要遍历一遍二叉树，才能知道它的深度，层序遍历时间复杂度也是O(n)，所以这道题的迭代法依旧是层序遍历的模板题，套入模板就行了。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int maxDepth(TreeNode* root) {
  15.         int depth = 0;      // 二叉树的深度
  16.         queue<TreeNode*> que;
  17.         if(root == NULL) return 0;
  18.         que.push(root);
  19.         while(!que.empty()){
  20.             int size = que.size();
  21.             for(int i = 0; i < size; i++){      // 遍历单层二叉树的节点
  22.                 TreeNode* cur = que.front();
  23.                 que.pop();
  24.                 if(cur->left) que.push(cur->left);
  25.                 if(cur->right) que.push(cur->right);
  26.             }
  27.             depth++;        // 深度加1
  28.         }
  29.         return depth;
  30.     }
  31. };

5.10、二叉树的最小深度

111. 二叉树的最小深度 - 力扣（LeetCode）

相对于104. 二叉树的最大深度，本题也还可以使用层序遍历的方式来解决，思路是一样的。
需要注意的是，只有当左右孩子都为空的时候，才说明遍历的节点是最低的叶子节点。如果其中一个孩子不为空，则不是最低点。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int minDepth(TreeNode* root) {
  15.         int minDepth = 0;       // 记录二叉树的最小深度
  16.         queue<TreeNode*> que;
  17.         if(root == nullptr) return 0;
  18.         que.push(root);
  19.         minDepth++;
  20.         while(!que.empty()){
  21.             int size = que.size();
  22.             for(int i = 0; i < size; i++){
  23.                 TreeNode* cur = que.front();
  24.                 que.pop();
  25.                 if(!cur->left && !cur->right){  // 只有当叶子节点的左右孩子都为空，说明改叶子节点是最低点
  26.                     return minDepth;
  27.                 }
  28.                 else{
  29.                     if(cur->left) que.push(cur->left);
  30.                     if(cur->right) que.push(cur->right);
  31.                 }
  32.             }
  33.             minDepth++;
  34.         }
  35.         return minDepth;
  36.     }
  37. };

5.11、总结

二叉树的层序遍历，就是图论中广度优先搜索在二叉树的应用，需要借助队列来实现（此时又发现队列的另一个应用了，慢慢积累吧！）
十道题我分了两天写！其实也不算两天，花的时间不多，每一道题都是自己写的再去看代码随想录，发现自己写的跟随想录几乎是一样的。这应该算是一点点小进步吧！希望有一天能写出比随想录更优的代码出来。

6、翻转二叉树

226. 翻转二叉树 - 力扣（LeetCode）

6.1、迭代法

思路：
迭代法：这是我比较擅长的

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     // 迭代法
  15.     TreeNode* invertTree(TreeNode* root) {
  16.         queue<TreeNode*> que;
  17.         if(root == nullptr) return root;
  18.         que.push(root);
  19.         while(!que.empty()){
  20.             int size = que.size();
  21.             for(int i = 0; i < size; i++){
  22.                 TreeNode* cur = que.front();
  23.                 que.pop();
  24.                 if(cur->left) que.push(cur->left);
  25.                 if(cur->right) que.push(cur->right);
  26.                 if(cur->left || cur->right){    // 如果当前节点存在左或者是右叶子节点，才需要翻转
  27.                     TreeNode* temp = cur->left;
  28.                     cur->left = cur->right;     // 左孩子节点指向右孩子节点
  29.                     cur->right = temp;          // 右孩子节点指向左孩子节点
  30.                 }
  31.             }
  32.         }
  33.         return root;
  34.     }
  35. };

6.2、递归法

这道题目是非常经典的题目，也是比较简单的题目（至少一看就会）。但正是因为这道题太简单，一看就会，导致很多同学没有抓到本质，稀里糊涂的就把这道题目过了（我就是！！）。这道题的重点应该放在递归法上，而不是迭代法，因为迭代法太简单了。
image.png
要翻转一棵二叉树，其实就是把它的当前节点的左右节点交换一下就可以了。

关键在于遍历顺序，前中后应该选择哪一种？（我虽然做对了，但是我根本就没有考虑遍历的顺序）。

注意，遍历的过程去翻转每一个节点的左右孩子就能达到整体翻转的效果
这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转两次！建议拿纸画一画，就理解了。

那么层序遍历可不可以呢？当然可以，我前面迭代法用的就是层序遍历。

递归法C++代码：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     // 迭代法(已解) || 递归法(已解)
  15.     /*
  16.     void recursion(TreeNode* node){     // 这是我的解法，写的比较外行
  17.         if(node == nullptr) return;
  18.         TreeNode* temp = node->left;
  19.         node->left = node->right;
  20.         node->right = temp;
  21.         recursion(node->left);
  22.         recursion(node->right);
  23.     }
  25.     TreeNode* invertTree(TreeNode* root) {
  26.         TreeNode* node = root;
  27.         recursion(node);
  28.         return root;
  29.     }
  30.     */
  31.     // 代码随想录的解法，其实大同小异，但是其中的思想相差甚远
  32.     // 前序、后序的方法都可以，唯独中序不行，中序会将一些节点翻转两次!!!
  33.     TreeNode* invertTree(TreeNode* root){
  34.         if(root == nullptr) return root;
  35.         swap(root->left, root->right);
  36.         invertTree(root->left);
  37.         invertTree(root->right);
  38.         return root;
  39.     }
  40. };

7、二叉树周末总结

代码随想录 - 二叉树 - 7、二叉树周末总结，这里总结的很好了。

8、对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

今天是除夕夜的前一天，感觉好累，这道题的解法思路就去看代码随想录里的题解吧
代码随想录 - 二叉树 - 8、对称二叉树

递归法：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     bool compare(TreeNode* left, TreeNode* right){
  15.         // 首先排除空节点的情况
  16.         if(left != NULL && right == NULL) return false;
  17.         else if(left == NULL && right != NULL) return false;
  18.         else if(left == NULL && right == NULL) return true;
  19.         else if(left->val != right->val) return false;
  21.         // 此时就是，左右节点都不为空且数值相等的情况
  22.         // 这个时候才做递归，做下一层的判断
  23.         bool outside = compare(left->left, right->right);       // 左子树：左，右子树：右
  24.         bool inside = compare(left->right, right->left);        // 左子树：右，右子树：左
  25.         bool isSame = outside && inside;                        // 左子树：中，右子树：中；逻辑判断
  26.         return isSame;
  27.     }
  29.     bool isSymmetric(TreeNode* root) {
  30.         if(root == NULL) return false;
  31.         return compare(root->left, root->right);
  32.     }
  33. };

迭代法：用栈和队列都能做，代码是一样的

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     bool compare(TreeNode* left, TreeNode* right){
  15.         // 首先排除空节点的情况
  16.         if(left != NULL && right == NULL) return false;
  17.         else if(left == NULL && right != NULL) return false;
  18.         else if(left == NULL && right == NULL) return true;
  19.         else if(left->val != right->val) return false;
  21.         // 此时就是，左右节点都不为空且数值相等的情况
  22.         // 这个时候才做递归，做下一层的判断
  23.         bool outside = compare(left->left, right->right);       // 左子树：左，右子树：右
  24.         bool inside = compare(left->right, right->left);        // 左子树：右，右子树：左
  25.         bool isSame = outside && inside;                        // 左子树：中，右子树：中；逻辑判断
  26.         return isSame;
  27.     }
  29.     bool isSymmetric(TreeNode* root) {
  30.         if(root == NULL) return false;
  31.         return compare(root->left, root->right);
  32.     }
  33. };

9、二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode）

递归法：

后序

  1. 确定递归函数的参数和返回值：参数就是传入的根节点，返回值就是这棵树的高度，所以返回值是int型。

    1. int getPath(treeNode* node);

  2. 确定递归出口：如果为空节点的话，就返回0，表示高度是0；

    1. if(node == nullptr) return 0;

  3. 确定单层递归逻辑：先求它的左子树的深度，再求它的右子树的深度，然后取左右深度最大的数值，再+1（加1是因为算上当前中间节点）就是目前节点为根节点的数的深度。

    1. int leftDepth = getPath(node->left);
    2. int rightDepth = getPath(node->right);
    3. int depth = 1 + max(leftDepth, rigthDepth);
    4. return depth;

    所以整体c++代码如下：

    1. class Solution{
    2. public:
    3.  int getPath(TreeNode* node){
    4.      if(node == nullptr) return 0;
    5.      int leftDepth = getPath(node->left);        // 左
    6.      int rightDepth = getPath(node->right);        // 右
    7.      int depth = 1 + max(leftDepth, rightDepth);    // 中
    8.      return depth;
    9.  }
    10.  int maxdepth(TreeNode* root){
    11.      return getPath(root);
    12.  }
    13. };

    代码精简之后：

    1. class Solution{
    2. public:
    3.  int maxdepth(TreeNode* root){
    4.      if(root == nullptr) return 0;
    5.      return 1 + max(getPath(node->left),getPath(node->right));
    6.  }
    7. };

    精简之后的代码根本看不出是哪种遍历方式，也看不出递归三部曲的步骤，所以如果对递归不是很熟练的话，尽量不要用这种装逼的代码！

前序（深度回溯）

本题当然也可以使用前序的方法来做，代码如下（充分表现出回溯的过程）

  1. class Solution{
  2. public:
  3.     int result = 0;
  4.     void getdepth(TreeNode* node, int depth){
  5.         result = result > depth ? result : depth;    // 中
  6.         if(node->left == nullptr && node->right == nullptr) return;
  8.         if(node->left){        // 左
  9.             depth++;        // 深度+1
  10.             getdepth(node->left, depth);
  11.             depth--;        // 回溯-1
  12.         }
  13.         if(node->right){    // 右
  14.             depth++;        // 深度+1
  15.             getdepth(node->right, depth);
  16.             depth--;        // 回溯-1
  17.         }
  19.         return;
  20.     }
  21.     int maxDepth(TreeNode* root){
  22.         if(root == nullptr) return result;
  23.         getdepth(root, 1);
  24.         return result;
  25.     }
  26. };

以上是为了把细节体现出来，代码简化一下：

  1. class Solution{
  2. public:
  3.     int result = 0;
  4.     void getdepth(TreeNode* node, int depth){
  5.         result = result > depth ? result : depth;    // 中
  6.         if(node->left == nullptr && node->right == nullptr) return;
  8.         if(node->left){        // 左
  9.             depth++;        // 深度+1
  10.             getdepth(node->left, depth);
  11.             depth--;        // 回溯-1
  12.         }
  13.         if(node->right){    // 右
  14.             depth++;        // 深度+1
  15.             getdepth(node->left, depth);
  16.             depth--;        // 回溯-1
  17.         }
  19.         return;
  20.     }
  21.     int maxDepth(TreeNode* root){
  22.         if(root == nullptr) return result;
  23.         getdepth(root, 1);
  24.         return result;
  25.     }
  26. };

迭代法：

见 二叉树 - 5、二叉树的层序遍历 - 5.9、二叉树的最大深度

9.1、N 叉树的最大深度

559. N 叉树的最大深度 - 力扣（LeetCode）

递归法：

后序遍历

  1. /*
  2. // Definition for a Node.
  3. class Node {
  4. public:
  5.     int val;
  6.     vector<Node*> children;
  8.     Node() {}
  10.     Node(int _val) {
  11.         val = _val;
  12.     }
  14.     Node(int _val, vector<Node*> _children) {
  15.         val = _val;
  16.         children = _children;
  17.     }
  18. };
  19. */
  21. // 递归法：后序
  22. class Solution {
  23. public:
  24.     int maxDepth(Node* root) {
  25.         int depth = 0;
  26.         if(root == nullptr) return depth;
  27.         for(int i = 0; i < root->children.size(); i++){
  28.             if(root->children[i]){
  29.                 depth =  max(depth, maxDepth(root->children[i]));
  30.             }
  31.         }
  32.         return depth + 1;
  33.     }
  34. };

前序（深度回溯）

  1. /*
  2. // Definition for a Node.
  3. class Node {
  4. public:
  5.     int val;
  6.     vector<Node*> children;
  8.     Node() {}
  10.     Node(int _val) {
  11.         val = _val;
  12.     }
  14.     Node(int _val, vector<Node*> _children) {
  15.         val = _val;
  16.         children = _children;
  17.     }
  18. };
  19. */
  21. // 递归法：前序(深度回溯)
  22. class Solution {
  23. public:
  24.     int result = 0;
  25.     void getPath(Node* node, int depth){
  26.         result = result > depth ? result : depth;           // 中
  27.         if(node->children.size() == 0) return;
  29.         for(int i = 0; i < node->children.size(); i++){
  30.             if(node->children[i]){                          // 从左到右
  31.                 depth++;    // 深度+1
  32.                 getPath(node->children[i], depth);
  33.                 depth--;    // 回溯-1
  34.             }
  35.         }
  36.         return;
  37.     }
  38.     int maxDepth(Node* root) {
  39.         if(root == nullptr) return result;
  40.         getPath(root, 1);
  41.         return result;
  42.     }
  43. };

迭代法

  1. /*
  2. // Definition for a Node.
  3. class Node {
  4. public:
  5.     int val;
  6.     vector<Node*> children;
  8.     Node() {}
  10.     Node(int _val) {
  11.         val = _val;
  12.     }
  14.     Node(int _val, vector<Node*> _children) {
  15.         val = _val;
  16.         children = _children;
  17.     }
  18. };
  19. */
  21. // 层序遍历法
  22. class Solution {
  23. public:
  24.     int maxDepth(Node* root) {
  25.         int depth = 0;
  26.         queue<Node*> que;
  27.         if(root == nullptr) return depth;
  28.         que.push(root);
  29.         while(!que.empty()){
  30.             int size = que.size();
  31.             for(int i = 0; i < size; i++){      // 处理当前这一层的节点
  32.                 Node* cur = que.front();
  33.                 que.pop();
  34.                 for(int j = 0; j < cur->children.size(); j++){
  35.                     if(cur->children[j]){
  36.                         que.push(cur->children[j]);
  37.                     }
  38.                 }
  39.             }
  40.             depth++;
  41.         }
  42.         return depth;
  43.     }
  44. };

10、二叉树的最小深度

递归法：后序遍历

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int minDepth(TreeNode* root) {
  15.         if(root == nullptr) return 0;
  16.         int left = minDepth(root->left);                        // 左
  17.         int right = minDepth(root->right);                      // 右
  18.                                                                 // 中
  19.         // 当一个左子树为空，右子树不为空，这时左子树并不是最低点
  20.         if(root->left == nullptr && root->right != nullptr){
  21.             return 1 + right;
  22.         }
  23.         // 当一个左子树不为空，右子树为空，这时右子树并不是最低点
  24.         if(root->left != nullptr && root->right == nullptr){
  25.             return 1 + left;
  26.         }
  27.         return 1 + min(left, right);
  28.     }
  29. };

迭代法

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int minDepth(TreeNode* root) {
  15.         int minDepth = 0;       // 记录二叉树的最小深度
  16.         queue<TreeNode*> que;
  17.         if(root == nullptr) return 0;
  18.         que.push(root);
  19.         minDepth++;
  20.         while(!que.empty()){
  21.             int size = que.size();
  22.             for(int i = 0; i < size; i++){
  23.                 TreeNode* cur = que.front();
  24.                 que.pop();
  25.                 if(!cur->left && !cur->right){
  26.                     return minDepth;
  27.                 }
  28.                 else{
  29.                     if(cur->left) que.push(cur->left);
  30.                     if(cur->right) que.push(cur->right);
  31.                 }
  32.             }
  33.             minDepth++;
  34.         }
  35.         return minDepth;
  36.     }
  37. };

11、完全二叉树的节点个数

222. 完全二叉树的节点个数 - 力扣（LeetCode）

完全二叉树只有两种情况，

  • 情况一：就是满二叉树
  • 情况二：最后一层叶子节点没有满

对于情况一，可以直接用 2^树深度 - 1 来计算，注意，这里根节点的深度是1
对于情况二：分别递归其左孩子，右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况一来计算。

完全二叉树如图所示：
image.png
可以看出，如果一棵树不是满二叉树，就递归其左右孩子，知道遇到满二叉树为止，用公式计算这棵子树（满二叉树）的节点数量。

C++代码如下：

  1. class Solution{
  2. public:
  3.     int countNodes(TreeNode* root){
  4.         if(root == nullptr) return 0;
  5.         TreeNode* left = root->left;
  6.         TreeNode* right = root->right;
  7.         int leftHeight = 0, rightHeight = 0;    // 这里初始化为0是有目的的，为了求下面指数方便
  8.         // 求左子树的深度
  9.         while(left){
  10.             left = left->left;
  11.             leftHeight++;
  12.         }
  13.         // 求右子树的深度
  14.         while(right){
  15.             right = right->right;
  16.             rightHeight++;
  17.         }
  18.         if(leftHeight == rightHeight){
  19.             return (2 << leftHeight) - 1;    // 注意 (2 << 1) 相当于 2^2,所以leftHeight初始化为0
  20.         }
  21.         // 如果当前节点所在的二叉树不是满二叉树
  22.         return countNodes(root->left) + countNodes(root->right) + 1;    // 1表示当前二叉树的根节点，需要加上
  23.     }
  24. };

12、平衡二叉树

110. 平衡二叉树 - 力扣（LeetCode）

题外话

image.png
因为求深度可以从上到下去查，所以通常使用前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）。所以在求二叉树的最大深度中，正确的逻辑应该是使用深度回溯的方法来解决。

本题思路

递归

此时大家应该明白了既然要求比较高度，必然是要前序遍历。
递归三部曲：

  1. 明确递归的参数和返回值
  • 参数：当前传入节点
  • 返回值：以当前传入节点为根节点的二叉树的高度。

那么如何标记左右子树的高度差大于1呢？
如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，继续返回树的高度的话已经没有意义了。
所以如果已经不是二叉平衡树了，可以返回-1来标记已经不符合平衡树的规则了。

  1. int getHeight(TreeNode* node);
  1. 明确终止条件
  • 递归的过程依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树的高度为0
    1. if(node == nullptr) return 0;
  1. 明确单层递归的逻辑
  • 如何判断以当前传入节点的二叉树是否是平衡二叉树呢？当然是左右子树的高度差大于1 ```cpp int leftHeight = getHeight(node->left); // 左 if(leftHeight == -1) return -1; int rightHeight = getHeight(node->right); // 右 if(rightHeight == -1) return -1;

int result; if(abs(leftHeight - rightHeight) > 1){ // 中 result = -1; } else{ result = 1 + max(leftHeight, rightHeight); // 以当前节点为根节点的树的最大高度 } return result;

  1. 代码精简之后：
  2. ```cpp
  3. int leftHeight = getHeight(node->left);
  4. if (leftHeight == -1) return -1;
  5. int rightHeight = getHeight(node->right);
  6. if (rightHeight == -1) return -1;
  7. return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);

此时递归的函数就已经写出来了，这个递归的函数传入节点指针，返回以该节点为根节点的二叉树的高度，如果不是二叉平衡树，则返回-1。
getHeight整体代码如下：

  1. int getHeight(TreeNode* node) {
  2.     if (node == NULL) {
  3.         return 0;
  4.     }
  5.     int leftHeight = getHeight(node->left);
  6.     if (leftHeight == -1) return -1;
  7.     int rightHeight = getHeight(node->right);
  8.     if (rightHeight == -1) return -1;
  9.     return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
  10. }

本题的整体递归代码如下：

  1. class Solution{
  2. public:
  3.     // 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了返回-1
  4.     int getHeight(TreeNode* node){
  5.         if(node == nullptr) return 0;
  6.         int leftHeight = getHeight(node->left);
  7.         if(leftHeight == -1) return -1;
  8.         int rightHeight = getHeight(node->right);
  9.         if(rightHeight == -1) return -1;
  10.         return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight,rightHeight);
  11.     }
  12.     bool isBalanced(TreeNode* node){
  13.         return getHeight(root) == -1 ? false : true;
  14.     }
  15. };

迭代

在 104. 二叉树的最大深度 中，我们可以使用层序遍历来求深度，但是就是不能直接使用层序遍历来求高度，这就体现出求高度和求深度的不同。

本题的迭代方法可以先定义一个函数，专门用来求高度。

这个函数通过栈模拟的后序遍历找每一个节点的高度（其实就是通过传入节点为根节点的最大深度来求的高度）

代码如下：

  1. // cur节点的最大深度，就是cur的高度
  2. int getDepth(TreeNode* cur) {
  3.     stack<TreeNode*> st;
  4.     if (cur != NULL) st.push(cur);
  5.     int depth = 0; // 记录深度
  6.     int result = 0;
  7.     while (!st.empty()) {
  8.         TreeNode* node = st.top();
  9.         if (node != NULL) {
  10.             st.pop();
  11.             st.push(node);                          // 中
  12.             st.push(NULL);
  13.             depth++;
  14.             if (node->right) st.push(node->right);  // 右
  15.             if (node->left) st.push(node->left);    // 左
  17.         } else {
  18.             st.pop();
  19.             node = st.top();
  20.             st.pop();
  21.             depth--;
  22.         }
  23.         result = result > depth ? result : depth;
  24.     }
  25.     return result;
  26. }

然后再用栈来模拟前序遍历，遍历每一个节点的时候，再去判断左右孩子的高度是否符合，代码如下：

  1. bool isBalanced(TreeNode* root){
  2.     stack<TreeNode*> st;
  3.     if(root == nullptr) return true;
  4.     st.push(root);
  5.     while(!st.empty()){
  6.         TreeNode* cur = st.top();                    // 中
  7.         st.pop();
  8.         if(abs(getDepth(root->left) - getDepth(root->right)) > 1){
  9.             return false;
  10.         }
  11.         if(node->right) st.push(node->right);        // 右
  12.         if(node->left) st.push(node->left);            // 左
  13.     }
  14.     return true;
  15. }

13、二叉树的所有路径

257. 二叉树的所有路径 - 力扣（LeetCode）

思路：
这道题要求从根节点到叶子节点的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。
在这道题目中第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径后再进入另一个路劲。

前序遍历以及回溯的过程如下：
image.png
我们先使用递归的方式来做前序遍历。要知道递归和回溯本来就是一家的，本题也需要使用到回溯。

递归

  1. 递归函数的参数以及返回值

要传入根节点，记录每一条路径的path，和存放结果集的result，这里的递归不需要返回值，代码如下：

  1. void traversal(TreeNode* cur, vector<int>& path, vector<string>& result)
  1. 确定递归的终止条件

本题的终止条件就是找到了叶子节点，即当cur不为空，且其左右孩子都为空的情况下，就算找到叶子节点

  1. if(cur->left == nullptr && cur->right == nullptr){
  2.     终止处理逻辑;
  3. }

为什么没有判断cur是否为空呢？因为下面的逻辑可以控制空节点不进入循环。
再来看一下终止处理的逻辑。
这里使用vector结构path来记录路径，所以要把vector结构的path转为string格式，再把这个string放入result里。

那么为什么使用了vector结构来记录路径呢？因为在下面处理单层递归逻辑的时候，要做回溯，使用vector方便来做回溯。
可能有的同学问了，我看有些人的代码也没有回溯啊。其实是有回溯的，只不过隐藏在函数调用时的参数赋值里了，下文我还会提到。

这里我们先使用vector结构的path容器来记录路径，那么终止处理逻辑如下：

  1. if(cur->left == nullptr && cur->right == nullptr){        // 遇到叶子节点
  2.     string sPath;
  3.     for(int i = 0; i < path.size() - 1; i++){            // 将path里记录的路径转为string格式
  4.         sPath += std::to_string(path[i]);
  5.         sPath += "->";
  6.     }
  7.     sPath += std::to_string(path[path.size() - 1]);        // 记录最后一个节点
  8.     result.push_back(sPath);                            // 收集一个路径
  9.     return;
  10. }
  1. 确定单层递归逻辑

因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路径上的节点，先放进path中。
path.push_back(cur->val);
然后是递归和回溯的过程，上面说过没有判断cur是否为空，那么在这里递归的时候，如果为空就不进行下一层递归了。
所以递归前要加上判断语句，下面要递归的节点是否为空，如下

  1. if (cur->left) {
  2.     traversal(cur->left, path, result);
  3. }
  4. if (cur->right) {
  5.     traversal(cur->right, path, result);
  6. }

此时还没完，递归完，要做回溯啊，因为path 不能一直加入节点，它还要删节点，然后才能加入新的节点。
那么回溯要怎么回溯呢，一些同学会这么写，如下：

  1. if (cur->left) {
  2.     traversal(cur->left, path, result);
  3. }
  4. if (cur->right) {
  5.     traversal(cur->right, path, result);
  6. }
  7. path.pop_back();

这个回溯就要很大的问题，我们知道，回溯和递归是一一对应的，有一个递归，就要有一个回溯，这么写的话相当于把递归和回溯拆开了， 一个在花括号里，一个在花括号外。

  1. if (cur->left) {
  2.     traversal(cur->left, path, result);
  3.     path.pop_back(); // 回溯
  4. }
  5. if (cur->right) {
  6.     traversal(cur->right, path, result);
  7.     path.pop_back(); // 回溯
  8. }

所以整体代码如下：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     // 1.参数类型和返回值类型 
  15.     // 2.递归出口
  16.     // 3.单层递归逻辑
  18.     void getPath(TreeNode* node, vector<int>& path, vector<string>& result){
  19.         path.push_back(node->val);
  20.         // 递归出口
  21.         if(node->left == nullptr && node->right == nullptr){
  22.             string sPath;
  23.             for(int i = 0; i < path.size() - 1; i++){
  24.                 sPath = sPath + std::to_string(path[i]);
  25.                 sPath = sPath + "->";
  26.             }
  27.             sPath = sPath + std::to_string(path[path.size() - 1]);
  28.             result.push_back(sPath);
  29.             return;
  30.         }
  31.         if(node->left){
  32.             getPath(node->left, path, result);
  33.             path.pop_back();
  34.         }
  35.         if(node->right){
  36.             getPath(node->right, path, result);
  37.             path.pop_back();
  38.         }
  39.         return;
  40.     }
  42.     vector<string> binaryTreePaths(TreeNode* root) {
  43.         vector<int> path;
  44.         vector<string> result;
  45.         getPath(root, path, result);
  46.         return result;
  47.     }
  48. };

迭代法

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<string> binaryTreePaths(TreeNode* root) {
  15.         stack<TreeNode*> treeSt;        // 保存遍历树的结点
  16.         stack<string> pathSt;           // 保存访问的路径
  17.         vector<string> result;          // 保存最终正确路径的结果集
  19.         if(root == nullptr) return result;
  21.         treeSt.push(root);
  22.         pathSt.push(std::to_string(root->val));
  23.         while(!treeSt.empty()){
  24.             TreeNode* node = treeSt.top();                  // 中
  25.             treeSt.pop();
  26.             string path = pathSt.top();
  27.             pathSt.pop();
  29.             if(node->left == nullptr && node->right == nullptr){
  30.                 result.push_back(path);
  31.             }
  32.             if(node->right){                                // 右
  33.                 treeSt.push(node->right);
  34.                 pathSt.push(path + "->" + std::to_string(node->right->val));
  35.             }
  36.             if(node->left){                                 // 左
  37.                 treeSt.push(node->left);
  38.                 pathSt.push(path + "->" + std::to_string(node->left->val));
  39.             }
  40.         }
  41.         return result;
  42.     }
  43. };

14、二叉树周末总结

想偷懒，总结还是去看代码随想录吧：代码随想录 - 二叉树 - 14、二叉树周末总结