二叉树的递归/层序遍历

递归遍历（DFS）

递归遍历二叉树代码如下：

class TreeNode{
    public:
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x): val(x),left(nullptr),right(nullptr);
};

void traverse(TreeNode* root){
    if(root == nullptr){
        return;
    }
    traverse(root->left);
    traverse(root->right);
}

这个二叉树是通过调用自己的本身去进行遍历每个节点的，这种在函数里面调用自己本身的方式就叫做递归。从整体上来看的话，这个遍历的顺序实际上是根据你先遍历左边还是右边来的，第一个traverse是遍历root的左子节点直到左子节点是nullptr的时候开始返回，然后到右子节点。但是如果先traverse是右子节点呢？那就是先访问右边的在到左边。

前序/中序/后序遍历

前序、中序、后序三种分别指的就是根节点的前、后、中的出场顺序，即【根节点、左子节点、右子节点】、【左子节点、根节点、右子节点】、【左子节点、右子节点、根节点】

class TreeNode{
    public:
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x): val(x),left(nullptr),right(nullptr);
};

void traverse(TreeNode* root){
    if(root == nullptr){
        return;
    }
    //前序遍历的地方
    traverse(root->left);
    //中序遍历的地方
    traverse(root->right);
    //后序遍历的地方
}

其实二叉树遍历的顺序是固定的，通过这个递归函数的话。只是如果在不同的地方去记录当前节点的时候，得到的顺序就会不一样，这就是前/中/后序遍历的区别所在。（这里借用一下我学习这篇文章的网站里的图像，二叉树的递归/层序遍历）

//前序遍历
vector<int> result;
void traverse(TreeNode* root){
    if(root == nullptr){
        return;
    }
    //前序遍历的地方
    result.push_back(root);
    traverse(root->left);
    //中序遍历的地方
    traverse(root->right);
    //后序遍历的地方
}

//后序遍历
vector<int> result;
void traverse(TreeNode* root){
    if(root == nullptr){
        return;
    }
    //前序遍历的地方
    traverse(root->left);
    //中序遍历的地方
    result.push_back(root);
    traverse(root->right);
    //后序遍历的地方

vector<int> result;
void traverse(TreeNode* root){
    if(root == nullptr){
        return;
    }
    //前序遍历的地方
    traverse(root->left);
    //中序遍历的地方
    traverse(root->right);
    //后序遍历的地方
    result.push_back(root);

最后result里面的顺序就是对应顺序遍历的结果。

由此我们可以看出这个二叉树遍历是很模版化的一个遍历方式。

层序遍历（BFS）

这里有三种写法，每种写法都有它的特点。层序遍历，顾名思义就是一层一层的遍历二叉树。

第一种写法

void levelOrderTraverse(TreeNode* root){
    if(root == nullptr){
        return;
    }

    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty())
    {
        TreeNode* cur = q.front();
        q.pop();
        //访问节点
        cout<< cur->val << endl;

        if(cur->left != nullptr){
            q.push(cur->left);
        }
        if(cur->right != nullptr){
            q.push(cur->right);
        }
    }
}

利用了队列的特性，将左右节点分别存入队列，并且每次循环都把队列最早入列的取出来并且访问。

第二种写法，加入了一个depth的特征，用来记录整个树访问的层数

void levelOrderTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    // 记录当前遍历到的层数（根节点视为第 1 层）
    int depth = 1;

    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode* cur = q.front();
            q.pop();
            // 访问 cur 节点，同时知道它所在的层数
            cout << "depth = " << depth << ", val = " << cur->val << endl;

            // 把 cur 的左右子节点加入队列
            if (cur->left != nullptr) {
                q.push(cur->left);
            }
            if (cur->right != nullptr) {
                q.push(cur->right);
            }
        }
        depth++;
    }
}

由于depth需要在访问完一层之后自增1，但是第一种写法的循环结束地方并不是一层访问完，而是一个节点被访问完并且将子节点入库之后算一次循环。所以为了使depth在一层访问完之后自增，所以添加了一个for循环在里面，for循环就是用来访问一层的，里面的

int sz = q.size();
for (int i = 0; i < sz; i++) {
    ...
}

能看出，sz这个变量就是记录这一层有多少个节点的。每次一层结束之后，q队列里面只剩下下一层的节点，所以在开头获取这个size就能代表着一层的节点数。

第三种写法

这种写法是在第二种的进阶版

回顾写法二，我们每向下遍历一层，就给 depth 加 1，可以理解为每条树枝的权重是 1，二叉树中每个节点的深度，其实就是从根节点到这个节点的路径权重和，且同一层的所有节点，路径权重和都是相同的。

那么假设，如果每条树枝的权重可以是任意值，现在让你层序遍历整棵树，打印每个节点的路径权重和，你会怎么做？

这样的话，同一层节点的路径权重和就不一定相同了，写法二这样只维护一个 depth 变量就无法满足需求了。

写法三就是为了解决这个问题，在写法一的基础上添加一个 State 类，让每个节点自己负责维护自己的路径权重和，代码如下：

class State {
public:
    TreeNode* node;
    int depth;

    State(TreeNode* node, int depth) : node(node), depth(depth) {}
};

void levelOrderTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    queue<State> q;
    // 根节点的路径权重和是 1
    q.push(State(root, 1));

    while (!q.empty()) {
        State cur = q.front();
        q.pop();
        // 访问 cur 节点，同时知道它的路径权重和
        cout << "depth = " << cur.depth << ", val = " << cur.node->val << endl;

        // 把 cur 的左右子节点加入队列
        if (cur.node->left != nullptr) {
            q.push(State(cur.node->left, cur.depth + 1));
        }
        if (cur.node->right != nullptr) {
            q.push(State(cur.node->right, cur.depth + 1));
        }
    }
}