1、二叉树理论基础

1.1、二叉树的种类

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

1.1.1、满二叉树

满二叉树：如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树。
如图所示：

这棵二叉树为满二叉树，也可以说是深度为k，有 2^k - 1 个节点的二叉树。

1.1.2、完全二叉树

什么是完全二叉树？

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

大家要看完全二叉树的定义，不要对完全二叉树的判断迷迷瞪瞪。
举个典型的例子：

之前我们刚刚讲过优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

1.1.3、二叉搜索树

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

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

下面这两棵树都是搜索树

1.1.4、平衡二叉搜索树

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

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

如图：

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

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

如果对数组和链表的增删查操作的时间复杂度还有疑问的，可以看一看这篇文章
链表和数组的插入删除时间复杂度都是o(n)，为什么教材网络上说链表效率高？

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

1.2、二叉树的存储方式

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

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

链式存储如图：

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

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

1.3、二叉树的遍历方式

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

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

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

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

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

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

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

大家可以对着如下图，看看自己理解的前后中序有没有问题。

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

1.4、二叉树的定义

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

struck TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL){}
};

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

2、二叉树的递归遍历

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

这里就不贴图了，题目比较简单。如果对基础的二叉树深度搜索的前中后序还有疑问的，可以看看一刷的笔记。

照例还是写递归三部曲：

1. 确定递归函数的参数和返回值
2. 确定终止条件

3. 确定单层递归的逻辑

   /**
   * Definition for a binary tree node.
   * 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) {}
   * };
   */
   class Solution {
   public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        preTraversal(root, result);
        return result;
    }
    // 前序递归
    void preTraversal(TreeNode* root, vector<int>& result){
        if(root == nullptr){
            return;
        }
        result.push_back(root->val);        // 中
        preTraversal(root->left, result);   // 左
        preTraversal(root->right, result);  // 右
    }
   };

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        midTraversal(root, result);
        return result;
    }
    // 中序递归 
    void midTraversal(TreeNode* root, vector<int>& result){
        if(root == nullptr){
            return;
        }
        midTraversal(root->left, result);   // 左
        result.push_back(root->val);        // 中
        midTraversal(root->right, result);  // 右
    }
};

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution{
public:
    vector<int> postorderTraversal(TreeNode* root){
        vector<int> result;
        postTraversal(root, result);
        return result;
    }
    // 后序递归 
    void postTraversal(TreeNode* root, vector<int>& result){
        if(root == nullptr){
            return;
        }
        postTraversal(root->left, result);   // 左
        postTraversal(root->right, result);  // 右
        result.push_back(root->val);        // 中
    }
};

3、二叉树的迭代遍历

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

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    // 迭代法实现前序遍历，且是统一风格的代码
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if(root == nullptr) return result;
        st.push(root);                  // 根节点先入栈
        while(!st.empty()){
            TreeNode* cur = st.top();
            if(cur != NULL){            // 如果节点非空，表明当前节点不是我们设置标志的节点
                st.pop();               // 如果当前节点非空，我们需要继续判断当前节点是否有左右孩子
                if(cur->right) st.push(cur->right);     // 右
                if(cur->left) st.push(cur->left);       // 左
                st.push(cur);                           // 中
                st.push(NULL);                          // 给当前节点设置标志
            }
            else{
                st.pop();                               // 弹出空指针(即我们设置的标志)
                result.push_back(st.top()->val);        // 这是我们想要操作的节点
                st.pop();
            }
        }
        return result;
    }
};

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    // 迭代法：统一风格的代码
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if(root == NULL) return result;
        st.push(root);
        while(!st.empty()){
            TreeNode* cur = st.top();
            if(cur != NULL){
                st.pop();
                if(cur->right) st.push(cur->right);
                st.push(cur);
                st.push(NULL);
                if(cur->left) st.push(cur->left);
            }
            else{
                st.pop();
                result.push_back(st.top()->val);
                st.pop();
            }
        }
        return result;
    }
};

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution{
public:
    vector<int> postorderTraversal(TreeNode* root){
        stack<TreeNode*> st;
        vector<int> result;
        if(root == NULL) return result;
        st.push(root);        // 根节点先入栈
        while(!st.empty()){
            TreeNode* node = st.top();
            if(node != NULL){    // 如果节点非空，表明当前节点不是我们设置标志的节点
                st.pop();
                st.push(node);                            // 中
                st.push(NULL);    // 给中节点设置标志
                if(node->right) st.push(node->right);    // 右
                if(node->left) st.push(node->left);        // 左
            }
            else{
                st.pop();        // 弹出空指针(即我们设置的标志)
                result.push_back(st.top()->val);        // 这是我们想要操作的节点
                st.pop();
            }
        }
        return result;
    }
};

4、二叉树的统一迭代法

在 3、二叉树的迭代遍历 我使用的就是统一的迭代法来解题的，虽然说不使用统一的解法也能把前中后序给求解出来，但是代码不同意，理解的角度也不太一样，为了方便记忆，以后就都使用统一的迭代法来解这种遍历的题目了。

5、二叉树的层序遍历

学会二叉树的层序遍历，可以一口气打完以下十题：

• 102.二叉树的层序遍历
• 107.二叉树的层次遍历II
• 199.二叉树的右视图
• 637.二叉树的层平均值
• 429.N叉树的层序遍历
• 515.在每个树行中找最大值
• 116.填充每个节点的下一个右侧节点指针
• 117.填充每个节点的下一个右侧节点指针II
• 104.二叉树的最大深度
• 111.二叉树的最小深度

5.1、二叉树的层序遍历

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

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。
需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。
使用队列实现二叉树广度优先遍历，动画如下：

这样就实现了层序从左到右遍历二叉树。
代码如下：这份代码也可以作为二叉树层序遍历的模板，打十个就靠它了。

C++代码：

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> que;
        if(root == NULL) return result;
        que.push(root);
        while(!que.empty()){
            vector<int> temp;           // 用一个临时的一维数组来存二叉树中一层的节点
            int size = que.size();      // 队列的大小,即二叉树当前这一层的节点数
            while(size--){
                TreeNode* cur = que.front();
                temp.push_back(cur->val);
                que.pop();
                if(cur->left) que.push(cur->left);      // 左节点非空就入队
                if(cur->right) que.push(cur->right);    // 右节点非空就入队
            }
            result.push_back(temp);
        }
        return result;
    }
};

此时我们就掌握了二叉树的层序遍历了，那么如下九道力扣上的题目，只需要修改模板的两三行代码（不能再多了），便可打倒！

5.2、二叉树的层序遍历 II

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

这道题目同样也是层序遍历，只不过输出的顺序是从二叉树的叶子节点所在的层到根节点所在的层，逐层从左向右遍历输出。

代码里有详细的解析

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    // 先按顺序自上向下的层序遍历，然后在最后面要输出的时候反转一下数组即可
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> que;
        if(root == nullptr){
            return result;
        }
        que.push(root);
        while(!que.empty()){
            vector<int> temp;           // 用一个临时数组来存储一层的节点元素值
            int size = que.size();      // 二叉树每一层的节点数
            while(size--){              // 遍历完一层才推出循环
                TreeNode* cur = que.front();
                temp.push_back(cur->val);
                que.pop();
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
            result.push_back(temp);
        }
        reverse(result.begin(), result.end());          // 在这里反转一下数组即可
        return result;
    }
};

5.3、二叉树的右视图

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

这道题还是层序遍历，只是要记录的是当前这一层左右边的节点而已，要实现也很简单，判断当前这一层的size等于等于最后一次循环是的值，就可以求解出来了

C++代码

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> que;
        if(root == nullptr){
            return result;
        }
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            while(size){
                TreeNode* cur = que.front();
                que.pop();
                if(size == 1){  // 如果是当前这一层中最右边的节点，那么需要把它加入到数组中
                    result.push_back(cur->val);
                }
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
                size--;         // 注意，因为while循环内我有size==1的判断条件，因此这里的size--不能放在while()里面 
            }
        }
        return result;
    }
};

5.4、二叉树的层平均值

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

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> result;
        queue<TreeNode*> que;
        if(root == nullptr){
            return result;
        }
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            int count = size;          // count是一个中间变量，也就是当前层的节点数
            double sum = 0;            // 当前这一层的和
            while(size--){
                TreeNode* cur = que.front();
                que.pop();
                sum += cur->val;
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
            result.push_back(sum / count);
        }
        return result;
    }
};

5.5、N 叉树的层序遍历

429. N 叉树的层序遍历

N叉树的层序遍历与二叉树的层序遍历简直就是一模一样的，一层之中的节点数由2个变成N个而已，没什么好讲的

C++代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) {
        val = _val;
    }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> result;
        queue<Node*> que;
        if(root == nullptr){
            return result;
        }
        que.push(root);
        while(!que.empty()){
            vector<int> temp;       // temp用来存储N叉树当前这一层的节点
            int size = que.size();
            while(size--){
                Node* cur = que.front();
                que.pop();
                temp.push_back(cur->val);
                // 遍历N个节点
                for(int i = 0; i < cur->children.size(); i++){
                    que.push(cur->children[i]);
                }
            }
            result.push_back(temp);
        }
        return result;
    }
};

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

515. 在每个树行中找最大值

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> que;
        if(root == nullptr){
            return result;
        }
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            int max = INT_MIN;
            while(size--){
                TreeNode* cur = que.front();
                que.pop();
                max = std::max(max, cur->val);
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
            result.push_back(max);
        }
        return result;
    }
};

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

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

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;
    Node() : val(0), left(NULL), right(NULL), next(NULL) {}
    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        if(root == NULL){
            return NULL;
        }
        queue<Node*> que;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            Node* pre = new Node(0);        // cur的前一个节点
            while(size){
                Node* cur = que.front();
                que.pop();
                pre->next = cur;            // 前一个节点的next指向当前节点
                if(size == 1){              // 如果是当前这一层的最右边节点，那么让它的next指向NULL
                    cur->next = NULL;
                }
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
                pre = cur;                  // 更新pre节点
                size--;
            }
        }
        return root;
    }
};

其实也可以不用申请 pre 节点，但是这样代码比较巧妙，有点不好想到

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;
    Node() : val(0), left(NULL), right(NULL), next(NULL) {}
    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        if(root == NULL){
            return NULL;
        }
        queue<Node*> que;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            while(size){
                Node* cur = que.front();
                que.pop();
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
                cur->next = que.front();    // 更新pre节点
                if(size == 1){              // 如果是当前这一层的最右边节点，那么让它的next指向NULL
                    cur->next = NULL;
                }
                size--;
            }
        }
        return root;
    }
};

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

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

这道题目说是二叉树，但116题目说是完整二叉树，其实没有任何差别，一样的代码一样的逻辑一样的味道

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;
    Node() : val(0), left(NULL), right(NULL), next(NULL) {}
    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        if(root == NULL){
            return NULL;
        }
        queue<Node*> que;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            while(size){
                Node* cur = que.front();
                que.pop();
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
                cur->next = que.front();
                if(size == 1){
                    cur->next = NULL;
                }
                size--;
            }
        }
        return root;
    }
};

5.9、二叉树的最大深度

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

简单一点的解法，层序遍历就行了，但是效率低。也可以用递归来做，在不是极端的情况下，递归的效率略高，但也没有好到哪里去

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr){
            return 0;
        }
        queue<TreeNode*> que;
        int depth = 0;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            while(size--){
                TreeNode* cur = que.front();
                que.pop();
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
            depth++;
        }
        return depth;
    }
};

5.10、二叉树的最小深度

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

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

题目交代的很清楚，当一个节点是叶子节点的时候，它所在的路径就是最短路径

C++代码如下：

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == nullptr){
            return 0;
        }
        queue<TreeNode*> que;
        int depth = 0;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            while(size--){
                TreeNode* cur = que.front();
                que.pop();
                if(!cur->left && !cur->right){
                    return ++depth;            // 如果是最短路径，直接return
                }
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
            depth++;
        }
        return depth;
    }
};

总结：
二叉树的层序遍历，就是图论中的广度优先搜索在二叉树中的应用，需要借助队列来实现（此时又发现队列的一个应用了）。
来吧，一口气打十个：

• 102.二叉树的层序遍历
• 107.二叉树的层次遍历II
• 199.二叉树的右视图
• 637.二叉树的层平均值
• 429.N叉树的前序遍历
• 515.在每个树行中找最大值
• 116.填充每个节点的下一个右侧节点指针
• 117.填充每个节点的下一个右侧节点指针II
• 104.二叉树的最大深度
• 111.二叉树的最小深度

致敬叶师傅！

6、翻转二叉树

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

6.1、递归法

要翻转整棵二叉树，思路就是翻转当前节点的左子树和右子树，然后递归这样的操作。

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

C++代码如下：

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr){
            return root;
        }
        if(root->left) invertTree(root->left);      // 左
        if(root->right) invertTree(root->right);    // 右
        // 中（这里代码冗余，但体现出逻辑性）
        if(root->left && root->right){
            swap(root->left, root->right);
        }
        else if(root->left && !root->right){
            swap(root->left, root->right);
        }
        else if(!root->left && root->right){
            swap(root->left, root->right);
        }
        return root;
    }
};

递归法简化：

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr){
            return root;
        }
        if(root->left) invertTree(root->left);      // 左
        if(root->right) invertTree(root->right);    // 右
        // 中
        swap(root->left, root->right);
        return root;
    }
};

6.2、迭代法

前序和后序都可以，都是一样的思路，稍微改一下代码就行了。我这里使用后序

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr){
            return root;
        }
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()){
            TreeNode* cur = st.top();           // 中
            st.pop();
            swap(cur->left, cur->right);
            if(cur->right) st.push(cur->right); // 右
            if(cur->left) st.push(cur->left);   // 左
        }
        return root;
    }
};

广度优先遍历

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if(root != nullptr){
            que.push(root);
        }
        while(!que.empty()){
            int size = que.size();
            for(int i = 0; i < size; i++){
                TreeNode* node = que.front();
                que.pop();
                swap(node->left, node->right);      // 交换节点
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return root;
    }
};

7、周末二叉树总结

代码随想录 - 二叉树 - 7、周末二叉树总结

8、对称二叉树

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

8.1、递归法**

递归三部曲

1. 确定递归函数的参数和返回值
2. 确定终止条件

3. 确定单层递归的逻辑

   /**
   * Definition for a binary tree node.
   * 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) {}
   * };
   */
   class Solution {
   public:
    bool isSymmetric(TreeNode* root) {
        return compare(root->left, root->right);
    }
    bool compare(TreeNode* left, TreeNode* right){
        // 首先排除空节点的情况
        if(left != nullptr && right == nullptr) return false;
        else if(left == nullptr && right != nullptr) return false;
        else if(left == nullptr && right == nullptr) return true;    // 这一步很关键,后面会细讲
        // 排除了空节点，再排除数值不相同的情况
        else if(left->val != right->val) return false;
        // 此时就是，左右节点都存在，且数值相等的情况，这个时候才有必要做递归操作
        bool inside = compare(left->right, right->left);            // 内测节点比较
        bool outsize = compare(left->left, right->right);            // 外侧节点比较
        bool insame = inside && outsize;
        return insame;
    }
   };

为什么下面的代码是错误的？

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return compare(root->left, root->right);
    }
    bool compare(TreeNode* left, TreeNode* right){
        // 首先排除空节点的情况
        if(left != nullptr && right == nullptr) return false;
        else if(left == nullptr && right != nullptr) return false;
        else if(left == nullptr && right == nullptr) return true;
        else if(left != nullptr && right != nullptr){
            if(left->val == right->val) return true;
            else return false;
        }
        // 此时就是，左右节点都存在，且数值相等的情况，这个时候才有必要做递归操作
        bool inside = compare(left->right, right->left);
        bool outsize = compare(left->left, right->right);
        bool insame = inside && outsize;
        return insame;
    }
};

举个例子，如果测试用例是下面这样

结果输出会是 true 。为什么？
因为第一次进入方法compare，left->val == right->val，这个时候还没进入递归就return true 了，当然不对了！
所以，我们要的是，如果两个节点进行比较，并且满足 left->val == right->val，不让它们退出，还要继续进行比较，直到 它们的孩子节点都为 nullptr，我们才认为 左子树 和 右子树 是对称的。
所以这就是为什么说else if(left == nullptr && right == nullptr) return true; 这一步是很关键的。

吃透这个思路，是递归法解出这道题目的关键。

8.2、迭代法

这道题目我们也可以使用迭代法，但要注意，这里的迭代法可不是前中后序的迭代写法，因为本题的本质是判断两个树是否是相互翻转的，其实已经不是所谓二叉树遍历的前中后序的关系了。

这里我们可以使用队列来比较两个树（根节点的左右子树）是否相互翻转，（注意这不是层序遍历），虽然也是一层一层访问节点，但是和层序遍历还是有很大区别的。

使用队列

如下的条件判断和递归的逻辑是一样的。
代码如下：

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> que;
        que.push(root->left);       // 将左子树头结点加入队列
        que.push(root->right);      // 将右子树头结点加入队列
        while(!que.empty()){        // 接下来判断左子树和右子树是否对称
            TreeNode* leftNode = que.front();
            que.pop();
            TreeNode* rightNode = que.front();
            que.pop();
            // 左节点为空、右节点为空，此时说明是对称的,这一步要先判断，不然后面可能会对空指针进行操作
            if(!leftNode && !rightNode) continue;
            // 左右一个节点不为空，或者都不为空但数值不相同，返回false
            else if(leftNode && !rightNode) return false;
            else if(!leftNode && rightNode) return false;    
            else if(leftNode->val != rightNode->val) return false;
            que.push(leftNode->right);      // 内测节点入队
            que.push(rightNode->left);
            que.push(leftNode->left);       // 外侧节点入队
            que.push(rightNode->right);
        }
        return true;
    }
};

细心的话，其实可以发现，这个迭代法，其实是把左右两个子树要比较的元素顺序放进一个容器，然后成对成对的取出来进行比较，那么其实使用栈也是可以的。只是这里不再是前中后序的遍历方式。

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        stack<TreeNode*> st;
        st.push(root->left);       // 将左子树头结点加入队列
        st.push(root->right);      // 将右子树头结点加入队列
        while(!st.empty()){        // 接下来判断左子树和右子树是否对称
            TreeNode* leftNode = st.top();
            st.pop();
            TreeNode* rightNode = st.top();
            st.pop();
            // 左节点为空、右节点为空，此时说明是对称的,这一步要先判断，不然后面可能会对空指针进行操作
            if(!leftNode && !rightNode) continue;
            // 左右一个节点不为空，或者都不为空但数值不相同，返回false
            else if(leftNode && !rightNode) return false;
            else if(!leftNode && rightNode) return false;    
            else if(leftNode->val != rightNode->val) return false;
            st.push(leftNode->right);      // 内测节点入队
            st.push(rightNode->left);
            st.push(leftNode->left);       // 外侧节点入队
            st.push(rightNode->right);
        }
        return true;
    }
};

逻辑和使用队列是一模一样的，只是比较的顺序不一样了。队列是内测节点先比较，而栈在不改变代码逻辑的情况下，是外侧节点先比较。

总结
在迭代法中我们使用了队列，需要注意的是这不是层序遍历，而且仅仅通过一个容器来成对的存放我们要比较的元素，知道这一本质之后就发现，用队列，用栈，甚至用数组，都是可以的。

9、二叉树的最大深度

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

9.1、递归法

本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。
而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。
这一点其实是很多同学没有想清楚的，很多题解同样没有讲清楚。
我先用后序遍历（左右中）来计算树的高度。

后序遍历C++代码如下：

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    int getDepth(TreeNode* root){
        if(root == nullptr) return 0;
        int leftDepth = getDepth(root->left);           // 左
        int rightDepth = getDepth(root->right);         // 右
        int depth = 1 + max(leftDepth, rightDepth);     // 中
        return depth;
    }
    int maxDepth(TreeNode* root) {
        return getDepth(root);
    }
};

后序遍历其实就是从树的底部往上走，每往上走一层，就记录一个深度，但其实本质是求这棵树的高度。

也可以使用前序遍历来做，(充分表现出求深度回溯的过程)

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    int result = 0;
    void getDepth(TreeNode* root, int depth){
        result = result > depth ? result : depth;   // 中
        if(root->left == nullptr && root->right == nullptr) return ;
        if(root->left){                             // 左
            getDepth(root->left, depth + 1);
        }
        if(root->right){                            // 右
            getDepth(root->right, depth + 1);
        }
        return;
    }
    int maxDepth(TreeNode* root) {
        if(root == nullptr) return result;
        getDepth(root, 1);
        return result;
    }
};

可以看出使用了前序（中左右）的遍历顺序，这才是真正求深度的逻辑！

9.2、迭代法

迭代法的话使用层序遍历是最合适的，迭代法算是一道模板题了

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        int depth = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            while(size--){
                TreeNode* cur = que.front();
                que.pop();
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
            depth++;
        }
        return depth;
    }
};

10、N叉树的最大深度

10.1、递归法

和求解9、二叉树的最大深度的思路是一样的。

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) {
        val = _val;
    }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    int result = 0;
    void getDepth(Node* root, int depth){
        result = result > depth ? result : depth;       // 中 ---这里是一定要在程序进来就处理的，不然会遗漏
        if(root->children.size() == 0){
            return;
        }
        for(int i = 0; i < root->children.size(); i++){ // 孩子节点
            getDepth(root->children[i], depth + 1);
        }
        return;
    }
    int maxDepth(Node* root) {
        if(root == NULL) return 0;
        getDepth(root, 1);
        return result;
    }
};

代码是最好的注释，后序遍历直接看代码吧

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) {
        val = _val;
    }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    int maxDepth(Node* root) {
        if(root == NULL) return 0;
        int depth = 1;
        for(int i = 0; i < root->children.size(); i++){
            depth = max(depth, 1 + maxDepth(root->children[i]));
        }
        return depth;
    }
};

10.2、迭代法

迭代法在之前5.5、N叉树的层序遍历的时候已经写过类似的了，不赘述

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) {
        val = _val;
    }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    int maxDepth(Node* root) {
        if(root == NULL) return 0;
        int depth = 0;
        queue<Node*> que;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            while(size--){
                Node* node = que.front();
                que.pop();
                for(int i = 0; i < node->children.size(); i++){
                    que.push(node->children[i]);
                }
            }
            depth++;
        }
        return depth;
    }
};

11、二叉树的最小深度

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

11.1、递归法**

前序遍历

这道题目，随想录只给出了后序遍历的做法（递归法用后序遍历确实是最理想的），于是我尝试用前序遍历来做，但是求不出来，前序遍历，每次都会遍历左子树直到底部，所以它就无法比较左右子树的深度，自然就无法求出二叉树的最小深度。

错误的代码

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    int result = 0;
    bool getdepth(TreeNode* root, int depth){
        result = result > depth ? result : depth;
        // 即使用标志位true和false来判断，也无法解决该题
        if(root->left == nullptr && root->right == nullptr){
            return false;
        }
        if(root->left){
            if(getdepth(root->left, depth + 1)){
                getdepth(root->left, depth + 1);
            }
            else{
                return false;
            }
        }
        if(root->right){
            if(getdepth(root->right, depth + 1)){
                getdepth(root->right, depth + 1);
            }
            else{
                return false;
            }
        }
        return true;
    }
    int minDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        getdepth(root, 1);
        return result;
    }
};