• 你只需要思考每一个节点应该做什么，其他的不用你管，抛给二叉树遍历框架，递归会对所有节点做相同的操作。
• 遇到一道二叉树的题目时的通用思考过程是：是否可以通过遍历一遍二叉树得到答案？如果不能的话，是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案? 如果需要用到子树信息, 一般使用后序遍历.

二叉树题目的递归（DFS）解法可以分两类思路：

1. 第一类是遍历一遍二叉树得出答案：对应着 回溯算法核心框架
2. 第二类是通过分解问题计算出答案：对应着 动态规划核心框架。

以求二叉树最大深度为例：

• 解法一：遍历一遍二叉树

[简单] 104. 二叉树的最大深度

• 解法二：分解问题。定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案

[简单] 104. 二叉树的最大深度

二叉树的解题思路就可以归类为上述两种思路：

1. 是否可以通过遍历一遍二叉树得到答案？
2. 如果不能的话，是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？

构建二叉树

根据层序遍历序列 {1, 2, 3, -1, -1, 4, 5} 构建二叉树：-1 代表 nullptr

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int num) : val(num), left(nullptr), right(nullptr) {}
};
int main()
{
    vector<int> nodeList = {1, 2, 3, -1, -1, 4, 5};     // -1 代表 nullptr
    TreeNode* root = new TreeNode(nodeList[0]);
    queue<TreeNode*> nodeQ;
    nodeQ.push(root);
    int idx = 1;
    while(!nodeQ.empty() && idx < nodeList.size())
    {
        TreeNode* cur = nodeQ.front();
        nodeQ.pop();
        if(nodeList[idx] != -1)
        {
            cur->left = new TreeNode(nodeList[idx]);
            nodeQ.push(cur->left);
        }
        if(idx + 1 < nodeList.size() && nodeList[idx + 1] != -1)
        {
            cur->right = new TreeNode(nodeList[idx + 1]);
            nodeQ.push(cur->right);
        }
        idx += 2;
    }
    while(!nodeQ.empty())
        nodeQ.pop();
    nodeQ.push(root);
    while(!nodeQ.empty())
    {
        int levelSize = nodeQ.size();
        for(int i = 0; i < levelSize; ++i)
        {
            TreeNode* cur = nodeQ.front();
            nodeQ.pop();
            cout << cur->val << " ";
            if(cur->left != nullptr)
                nodeQ.push(cur->left);
            if(cur->right != nullptr)
                nodeQ.push(cur->right);
        }
        cout << endl;
    }
    return 0;
}