二叉树是一种更为典型的树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。

二叉树的遍历

先（前）序遍历

前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。(根-左->右)

  1. class Solution {
  2. public:
  3.     vector<int> preorderTraversal(TreeNode* root) {
  4.         dfs(root);
  5.         return res;
  6.     }
  7. private:
  8.     vector<int> res;
  9.     void dfs(TreeNode* root)
  10.     {
  11.         if (root == nullptr) return;
  12.         res.push_back(root->val);
  13.         dfs(root->left);
  14.         dfs(root->right);
  15.     }
  16. };

中序遍历

中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。（左->根->右）

通常来说，对于二叉搜索树，我们可以通过中序遍历得到一个递增的有序序列。

  1. class Solution {
  2. public:
  3.     vector<int> inorderTraversal(TreeNode* root) {
  4.         dfs(root);
  5.         return res;
  6.     }
  7. private:
  8.     vector<int> res;
  9.     void dfs(TreeNode* root)
  10.     {
  11.         if (root == nullptr) return;
  12.         dfs(root->left);
  13.         res.push_back(root->val);
  14.         dfs(root->right);
  15.     }
  16. };

后序遍历

后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。（左->右->根）

  1. class Solution {
  2. public:
  3.     vector<int> postorderTraversal(TreeNode* root) {
  4.         dfs(root);
  5.         return res;
  6.     }
  7. private:
  8.     vector<int> res;
  9.     void dfs(TreeNode* root)
  10.     {
  11.         if (root == nullptr) return;
  12.         dfs(root->left);
  13.         dfs(root->right);
  14.         res.push_back(root->val);
  15.     }
  16. };

层序遍历

层序遍历就是逐层遍历树结构。
广度优先搜索是一种广泛运用在树或图这类数据结构中，遍历或搜索的算法。 该算法从一个根节点开始，首先访问节点本身。 然后遍历它的相邻节点，其次遍历它的二级邻节点、三级邻节点，以此类推。
当我们在树中进行广度优先搜索时，我们访问的节点的顺序是按照层序遍历顺序的。

通常，我们使用一个叫做队列的数据结构来帮助我们做广度优先搜索

  1. class Solution {
  2. public:
  3.     vector<vector<int>> levelOrder(TreeNode* root) {
  4.         bfs(root);
  5.         return res;
  6.     }
  7. private:
  8.     vector<vector<int>> res;
  9.     queue<TreeNode*> que;
  10.     void bfs(TreeNode* root)
  11.     {
  12.         if (root != nullptr) que.push(root);
  13.         while(!que.empty())
  14.         {
  15.             int n = que.size();
  16.             vector<int> tmp;
  17.             for (int i = 0; i < n; i++)
  18.             {
  19.                 TreeNode* cur = que.front();
  20.                 que.pop();
  21.                 tmp.push_back(cur->val);
  22.                 if (cur->left != nullptr) que.push(cur->left);
  23.                 if (cur->right != nullptr) que.push(cur->right);
  24.             }
  25.             res.push_back(tmp);
  26.         }
  27.     }
  28. };

这里要注意队列的大小要用变量保存， 因为for循环过程中队列大小发生了改变

递归求解树的问题

自顶向下

当遇到树问题时，请先思考一下两个问题：

  • 你能确定一些参数，从该节点自身解决出发寻找答案吗？
  • 你可以使用这些参数和节点本身的值来决定什么应该是传递给它子节点的参数吗？

如果答案都是肯定的，那么使用 “自顶向下” 的递归来解决此问题。

自底向上

对于树中的任意一个节点，如果你知道它子节点的答案，你能计算出该节点的答案吗？
如果答案是肯定的，那么 “自底向上” 的递归可能是一个不错的解决方法。

题目：二叉树的最大深度

  1. class Solution {
  2. public:
  3.     int maxDepth(TreeNode* root) {
  4.         dfs(root, 1);
  5.         return res;
  6.     }
  7. private:
  8.     int res = 0;
  9.     void dfs(TreeNode* root, int depth)
  10.     {
  11.         if (!root) return;
  12.         if (!root->left && !root->right)
  13.         {
  14.             res = max(res, depth);
  15.         }
  16.         dfs(root->left, depth + 1);
  17.         dfs(root->right, depth + 1);
  18.     }
  20. };

题目：对称二叉树

image.png

  1. class Solution {
  2. public:
  3.     bool isSymmetric(TreeNode* root) {
  4.         if (!root) return true;
  5.         return dfs(root->left, root->right);
  6.     }
  8. private:
  9.     bool dfs(TreeNode* left, TreeNode* right)
  10.     {
  11.         if (!left && !right) return true;
  12.         if (!left || !right || left->val != right->val)
  13.             return false;
  14.         return dfs(left->left, right->right) && dfs(left->right, right->left);
  15.     }
  17. };

题目：从中序与后序遍历序列构造二叉树

后序遍历的最后一个节点为根节点，从中序列表中找出根节点位置，左边为左子树，右边为右子树，接着递归即可