种类

满二叉树

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树
image.png

完全二叉树

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
image.png
之前我们刚刚讲过优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

二叉搜索树

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

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

image.png

平衡二叉搜索树

平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
image.png
C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn，注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_map底层实现是哈希表。

二叉树的存储方式

链式存储

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

顺序存储

其实就是用数组来存储二叉树
image.png

如果父节点的数组下标是 i，那么它的左孩子就是 i 2 + 1，右孩子就是 i 2 + 2。

二叉树的遍历方式

深度优先遍历

  • 前序遍历（递归法，迭代法）
  • 中序遍历（递归法，迭代法）
  • 后序遍历（递归法，迭代法）

这里前中后，其实指的就是中间节点的遍历顺序，只要大家记住 前中后序指的就是中间节点的位置就可以了。
之前我们讲栈与队列的时候，就说过栈其实就是递归的一种是实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的。
image.png

广度优先遍历

  • 层次遍历（迭代法）

而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树

二叉树的定义

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

二叉树的递归遍历

递归三要素：

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

    前序

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

    中序

    1. void traversal(TreeNode* cur, vector<int>& vec) {
    2.  if (cur == NULL) return;
    3.  traversal(cur->left, vec);  // 左
    4.  vec.push_back(cur->val);    // 中
    5.  traversal(cur->right, vec); // 右
    6. }

    后序

    1. void traversal(TreeNode* cur, vector<int>& vec) {
    2.  if (cur == NULL) return;
    3.  traversal(cur->left, vec);  // 左
    4.  traversal(cur->right, vec); // 右
    5.  vec.push_back(cur->val);    // 中
    6. }

二叉树的迭代遍历

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中
用栈也可以是实现二叉树的前后中序遍历了

前序遍历（迭代法）

前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。
为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序
二叉树 - 图8

  1.     vector<int> preorderTraversal(TreeNode* root) {
  2.         stack<TreeNode*> stk;
  3.         vector<int> result;
  4.         if (root == NULL)
  5.             return result;
  6.         stk.push(root);
  7.         while (!stk.empty())
  8.         {
  9.             TreeNode* cur = stk.top();
  10.             result.push_back(cur->val);
  11.             stk.pop();
  12.             if (cur->right)
  13.                 stk.push(cur->right);
  14.             if (cur->left)
  15.                 stk.push(cur->left);
  16.         }
  17.         return result;
  18.     }

中序遍历（迭代法）

那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。
那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。
二叉树 - 图9

  1.     vector<int> inorderTraversal(TreeNode* root) {
  2.         stack<TreeNode*> stk;
  3.         vector<int> result;
  4.         TreeNode* cur = root;
  5.         while (cur != NULL || !stk.empty())
  6.         {
  7.             if (cur == NULL){
  8.                 stk.push(cur);
  9.                 cur = cur->left;
  10.             }
  11.             else{
  12.                 cur = stk.top();
  13.                 stk.pop();
  14.                 result.push_back(cur->val);
  15.                 cur = cur->right;
  16.             }
  17.         }
  18.         return result;
  19.     }

后序遍历（迭代法）

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

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

二叉树的统一迭代法

相比迭代法， 只用调换两行代码的顺序
那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。
如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。
前序：

  2.     vector<int> preorderTraversal(TreeNode* root) {
  3.         stack<TreeNode*> stk;
  4.         vector<int> result;
  5.         TreeNode* cur;
  6.         if (root != NULL)
  7.             stk.push(root);
  8.         while (!stk.empty()) {
  9.             cur = stk.top();
  10.             if (cur != NULL)
  11.             {
  12.                 stk.pop();
  13.                 if (cur->right)
  14.                     stk.push(cur->right);
  15.                 if (cur->left)
  16.                     stk.push(cur->left);
  17.                 stk.push(cur);
  18.                 stk.push(NULL);
  20.             }
  21.             else
  22.             {
  23.                 stk.pop();
  24.                 cur = stk.top();
  25.                 stk.pop();
  26.                 result.push_back(cur->val);
  27.             }
  28.         }
  29.         return result;
  30.     }

中序：

  1.     //中序
  2.     vector<int> inorderTraversal(TreeNode* root) {
  3.         stack<TreeNode*> stk;
  4.         vector<int> result;
  5.         TreeNode* cur;
  6.         if (root != NULL)
  7.             stk.push(root);
  8.         while (!stk.empty()){
  9.             cur = stk.top();
  10.             if (cur != NULL)
  11.             {
  12.                 stk.pop();
  13.                 if (cur->right)
  14.                     stk.push(cur->right);
  15.                 stk.push(cur);
  16.                 stk.push(NULL);
  17.                 if (cur->left)
  18.                     stk.push(cur->left);
  19.             }
  20.             else
  21.             {
  22.                 stk.pop();
  23.                 cur = stk.top();
  24.                 stk.pop();
  25.                 result.push_back(cur->val);
  26.             }
  27.         }
  28.         return result;
  29.     }

后序：

  1.     vector<int> postorderTraversal(TreeNode* root) {
  2.         stack<TreeNode*> stk;
  3.         vector<int> result;
  4.         TreeNode* cur;
  5.         if (root != NULL)
  6.             stk.push(root);
  7.         while (!stk.empty()) {
  8.             cur = stk.top();
  9.             if (cur != NULL)
  10.             {
  11.                 stk.pop();
  12.                 stk.push(cur);
  13.                 stk.push(NULL);
  14.                 if (cur->right)
  15.                     stk.push(cur->right);
  16.                 if (cur->left)
  17.                     stk.push(cur->left);
  18.             }
  19.             else
  20.             {
  21.                 stk.pop();
  22.                 cur = stk.top();
  23.                 stk.pop();
  24.                 result.push_back(cur->val);
  25.             }
  26.         }
  27.         return result;
  28.     }

二叉树的层序遍历

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。
二叉树 - 图11
模板:

  1. class Solution {
  2. public:
  3.     vector<vector<int>> levelOrder(TreeNode* root) {
  4.         queue<TreeNode*> que;
  5.         if (root != NULL) que.push(root);
  6.         vector<vector<int>> result;
  7.         while (!que.empty()) {
  8.             int size = que.size();
  9.             vector<int> vec;
  10.             // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
  11.             for (int i = 0; i < size; i++) {
  12.                 TreeNode* node = que.front();
  13.                 que.pop();
  14.                 vec.push_back(node->val);
  15.                 if (node->left) que.push(node->left);
  16.                 if (node->right) que.push(node->right);
  17.             }
  18.             result.push_back(vec);
  19.         }
  20.         return result;
  21.     }
  22. };

题目：

102. 二叉树的层序遍历

107. 二叉树的层序遍历 II

199. 二叉树的右视图

637. 二叉树的层平均值

429. N 叉树的层序遍历

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

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

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

104. 二叉树的最大深度

111. 二叉树的最小深度

https://github.com/kaixuhuang/CPP/blob/master/binarytree/level-order-traversal.cpp
https://github.com/kaixuhuang/CPP/blob/master/binarytree/level-traver-traversal2.cpp

翻转二叉树

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

226. 翻转二叉树

https://github.com/kaixuhuang/CPP/blob/master/binarytree/reversal.cpp


对称二叉树

101. 对称二叉树

其实我们要比较的是两个树（这两个树是根节点的左右子树）
image.png
正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。

100. 相同的树

572. 另一棵树的子树

二叉树的最大深度

104. 二叉树的最大深度

递归法

本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。
而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。

迭代法

使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。

二叉树的最小深度

image.png
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。，注意是叶子节点。
什么是叶子节点，左右孩子都为空的节点才是叶子节点！

111. 二叉树的最小深度

递归法

求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。

  1. class Solution {
  2. public:
  3.     int getDepth(TreeNode* node) {
  4.         if (node == NULL) return 0;
  5.         int leftDepth = getDepth(node->left);           // 左
  6.         int rightDepth = getDepth(node->right);         // 右
  7.                                                         // 中
  8.         // 当一个左子树为空，右不为空，这时并不是最低点
  9.         if (node->left == NULL && node->right != NULL) { 
  10.             return 1 + rightDepth;
  11.         }   
  12.         // 当一个右子树为空，左不为空，这时并不是最低点
  13.         if (node->left != NULL && node->right == NULL) { 
  14.             return 1 + leftDepth;
  15.         }
  16.         int result = 1 + min(leftDepth, rightDepth);
  17.         return result;
  18.     }
  20.     int minDepth(TreeNode* root) {
  21.         return getDepth(root);
  22.     }
  23. };

迭代法

层序遍历
需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

完全二叉树的节点个数

222. 完全二叉树的节点个数

递归

  1. class Solution {
  2. private:
  3.     int getNodesNum(TreeNode* cur) {
  4.         if (cur == NULL) return 0;
  5.         int leftNum = getNodesNum(cur->left);      // 左
  6.         int rightNum = getNodesNum(cur->right);    // 右
  7.         int treeNum = leftNum + rightNum + 1;      // 中
  8.         return treeNum;
  9.     }
  10. public:
  11.     int countNodes(TreeNode* root) {
  12.         return getNodesNum(root);
  13.     }
  14. };


迭代法

层序迭代法

平衡二叉树

110. 平衡二叉树

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1

递归

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

迭代

当然此题用迭代法，其实效率很低，因为没有很好的模拟回溯的过程，所以迭代法有很多重复的计算。
虽然理论上所有的递归都可以用迭代来实现，但是有的场景难度可能比较大。

二叉树的所有路径

257. 二叉树的所有路径

使用回溯
这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。

递归

回溯和递归是一一对应的，有一个递归，就要有一个回溯
所以回溯要和递归永远在一起，世界上最遥远的距离是你在花括号里，而我在花括号外！

  1. class Solution {
  2. private:
  4.     void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
  5.         path.push_back(cur->val);
  6.         // 这才到了叶子节点
  7.         if (cur->left == NULL && cur->right == NULL) {
  8.             string sPath;
  9.             for (int i = 0; i < path.size() - 1; i++) {
  10.                 sPath += to_string(path[i]);
  11.                 sPath += "->";
  12.             }
  13.             sPath += to_string(path[path.size() - 1]);
  14.             result.push_back(sPath);
  15.             return;
  16.         }
  17.         if (cur->left) {
  18.             traversal(cur->left, path, result);
  19.             path.pop_back(); // 回溯
  20.         }
  21.         if (cur->right) {
  22.             traversal(cur->right, path, result);
  23.             path.pop_back(); // 回溯
  24.         }
  25.     }
  27. public:
  28.     vector<string> binaryTreePaths(TreeNode* root) {
  29.         vector<string> result;
  30.         vector<int> path;
  31.         if (root == NULL) return result;
  32.         traversal(root, path, result);
  33.         return result;
  34.     }
  35. };
  1. class Solution {
  2. private:
  4.     void traversal(TreeNode* cur, string path, vector<string>& result) {
  5.         path += to_string(cur->val); // 中
  6.         if (cur->left == NULL && cur->right == NULL) {
  7.             result.push_back(path);
  8.             return;
  9.         }
  10.         if (cur->left) traversal(cur->left, path + "->", result); // 左
  11.         if (cur->right) traversal(cur->right, path + "->", result); // 右
  12.     }
  14. public:
  15.     vector<string> binaryTreePaths(TreeNode* root) {
  16.         vector<string> result;
  17.         string path;
  18.         if (root == NULL) return result;
  19.         traversal(root, path, result);
  20.         return result;
  22.     }
  23. };