二叉树层序遍历大法好！_对下图所示的二叉树进行层序遍历

层序遍历

顾名思义，层序遍历就是把二叉树按层遍历，一层一层从根节点往深度方向遍历，每到新的一层，就把该层的所有节点遍历一遍，再进入下一层。

举个栗子⑧：
我们将下图中的二叉树划分为3层，并给每个节点按层从上到下，每层从左到右编上号码。
现在我们要求得该二叉树的层序遍历序列，步骤如下：

1.进入第0层，只有一个节点，将节点值添加入数组【1】；由于本层再无节点，进入下一层。
2.在第1层，有两个节点，从左至右将其节点值加入数组【1,2,3】，进入下一层
3.在第3层，有3个节点，不再赘述，我们将得到【1,2,3,4,5,6】,二叉树深度已到达最深，返回数组【1,2,3,4,5,6】

由于我们现在可以知道这个二叉树长啥模样，所以很容易写出其层序遍历序列。但现在是要编代码解决任意二叉树的层序遍历序列，输入仅仅是一棵二叉树。该如何写出层序遍历的代码呢？

为了适应今天LeetCode题目，我们将层序输出序列形式该为下列形式：

[[1],//第0层节点值
[2,3],//第1层节点值
[4,5,6]]//第2层节点值
1
2
3

即一维数组变为二维数组，二维数组的每一个元素都是二叉树每层的节点值数组。

二叉树的层序遍历：LeetCode102

现在分析层序遍历序列如何得到：
我们先准备两个一维数组，存储节点（这意味数组类型是struct TreeNode*）。再准备一个二维数组，存储结果

[[],//第0层
[],//第1层
[]]//第2层
1
2
3

至于二维数组的元素数目如何确定，计算树深即可：

int Depth(struct TreeNode* root){
     if(!root)
        return 0;
    int h_l = Depth(root->left)+1;//左子树深度
    int h_r = Depth(root->right)+1;//右子树深度
    return h_l>h_r?h_l:h_r;//返回最大树深
 }
1
2
3
4
5
6
7

将第0层的节点1放入q1[0]
第一次：进入层数0<树深3成立

由于节点1是根节点，本层就它一个，我们让q1[0]->val成为二维数组的第一个元素。即

[[1],//第0层
[],//第1层
[]]//第2层
1
2
3

接下来检查q1[0]左右孩子存不存在：
先检查左孩子存不存在，存在，放入q2[0]，接着检查右孩子，存在则放入q2[1];如下：

现在q1中的节点1已经失去了利用价值，因为它的节点值我们已经保存，且利用它找到了下一层的所有节点，所以可以丢弃它了。

为了逻辑的简单，我们视q2数组为一个中转站，它的意义仅仅是为我们暂时保存下一层所有节点。我们仅从q1中获取层序遍历的值，那么势必q2的内容要交给q1。接下来我们将q2的内容交给q1，把q2清空。进入层数+1；

第二次，进入层数1<树深3，成立
我们接着把q1[0]->val,q1[1]->val当做二维数组的第二个元素，即

[[1],//第0层
[2,3],//第1层
[]]//第2层
1
2
3

接下来检查q1[0]，q1[1]左右孩子存不存在：
先检查左孩子存不存在，存在，放入q2，接着检查右孩子，存在则放入q2;如下：

q1的内容再次失去了利用价值，用q2内容覆盖q1，清空q2。进入层数+1
第三次，进入层数2<树深3，成立
我们接着把q1[0]->val,q1[1]->val,q1[2]->val当做二维数组的第三个元素，即

[[1],//第0层
[2,3],//第1层
[4,5,6]]//第2层
1
2
3

接下来检查q1[0]，q1[1]左右孩子存不存在：都不存在，q2为空。继续q2覆盖q1(q2为什么为空还要覆盖q1？)。进入层数+1。

第四次，进入层数3不小于树深3，退出，返回结果。
经过上述步骤，我们即可得到层次遍历序列[[1],[2,3],[4,5,6]]

小伙伴们做起来！
二叉树的层序遍历

Code

int Depth(struct TreeNode* root){
     if(!root)
        return 0;
    int h_l = Depth(root->left)+1;
    int h_r = Depth(root->right)+1;
    return h_l>h_r?h_l:h_r;
 }
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    if(!root){
        *returnSize = 0;
        return NULL;
    }
    *returnSize = Depth(root);
    *returnColumnSizes = (int*)malloc(sizeof(int)*(*returnSize));
    int** res = (int**)malloc(sizeof(int*)*(*returnSize));

    struct TreeNode *q1[1000],*q2[1000];
    int q1_size = 0,q2_size = 0;
    q1[0] = root;
    q1_size++;
    int level = 0;
    while(level<*returnSize){
        res[level] = (int*)malloc(sizeof(int)*q1_size);
        for(int  i = 0;i<q1_size;i++)
            res[level][i] = q1[i]->val;
        (*returnColumnSizes)[level] = q1_size;
        for(int i = 0;i<q1_size;i++){
            if(q1[i]->left)
                q2[q2_size++] = q1[i]->left;
            if(q1[i]->right)
                q2[q2_size++] = q1[i]->right;
        }
        memcpy(q1,q2,sizeof(struct TreeNode)*q2_size);
        q1_size = q2_size,q2_size = 0;
        level++;
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

二叉树的层序遍历II：LeetCode107

这道题与上一道题并无二致，无非就是我们在将节点值填入二维数组的时候，注意这一层应该放在哪个位置罢了。如果上图的树按层序遍历来，会得到如下结果：

[[3],//第0层    对比本题结果 [[15,7],//第2层
[9,20],//第1层             [9,20], //第1层
[15,7]]//第2层             [3]]    //第0层
1
2
3

左右结果层数加起来

0 + 2 = 2
1 + 1 = 2
2 + 0 = 2
1
2
3

规律显而易见，那么该题的代码只需在102题的一个索引处改动即可：

将该索引改为[*returnSize-1-level]即可

试一下？
二叉树的层序遍历II

二叉树的锯齿形层序遍历：LeetCode103

先对比，找规律，再说话：

			在二维数组中的索引                     
[[3],//第0层     0     对比本题结果 [[3],//第0层
[9,20],//第1层   1                [20,9], //第1层
[15,7]]//第2层   2                [15,7]]    //第2层
1
2
3
4

规律显而易见，索引为奇数的一维数组需要将所有元素颠倒对换。
那么该题的代码只需在102题的代码之后加一个处理过程即可：

【奇数索引一维数组元素翻转Code】

for(int i = 1;i<level;i+=2){
    int top = (*returnColumnSizes)[i];
    for(int j = 0;j<top/2;j++){
        int tmp = res[i][j];
        res[i][j] = res[i][top-j-1];
        res[i][top-j-1] = tmp;
     }
 }
1
2
3
4
5
6
7
8

找树左下角的值：LeetCode513

你看，这道题只需要求最深那一层的最值左边的值，我们也就不用保存每一层的值进二维数组，只需要进最后一层，找到第一个节点，返回其值即可。

不如试试？

找树左下角的值

Code

int Height(struct TreeNode* root){
    if(!root)
        return 0;
    int h_l = Height(root->left) + 1;
    int h_r = Height(root->right) + 1;
    return h_l>h_r?h_l:h_r;
}
int findBottomLeftValue(struct TreeNode* root){
    int layer = Height(root);
    struct TreeNode* q1[1000],*q2[1000];
    int q1_size = 1,q2_size = 0;
    q1[0] = root;
    int h  = 0;
    int res;
    while(h<layer){
        if(h == layer - 1){
            res = q1[0]->val;
            break;
        }
        for(int i = 0;i<q1_size;i++){
            if(q1[i]->left)
                q2[q2_size++] = q1[i]->left;
            if(q1[i]->right)
                q2[q2_size++] = q1[i]->right;
        }
        memcpy(q1,q2,sizeof(struct TreeNode*)*q2_size);
        q1_size = q2_size,q2_size = 0;
        h++;
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

层数最深叶子节点的和：LeetCode1302

一样的道理，不用保存每一层的节点值，只需要在最后一层时，将所有节点值加起来返回即可

你看，一样的套路，你就试试呗！

层数最深叶子节点的和

Code

int Height(struct TreeNode* root){
    if(!root)
        return 0;
    int h_l = Height(root->left) + 1;
    int h_r = Height(root->right) + 1;
    return h_l>h_r?h_l:h_r;
}
int deepestLeavesSum(struct TreeNode* root){
    int layer = Height(root);
    struct TreeNode* q1[10000],*q2[10000];
    int q1_size = 1,q2_size = 0;
    q1[0] = root;
    int h  = 0;
    int sum = 0;
    while(h<layer){
        if(h == layer - 1){
            for(int i = 0;i<q1_size;i++)
                sum+=q1[i]->val;
            break;
        }
        for(int i = 0;i<q1_size;i++){
            if(q1[i]->left)
                q2[q2_size++] = q1[i]->left;
            if(q1[i]->right)
                q2[q2_size++] = q1[i]->right;
        }
        memcpy(q1,q2,sizeof(struct TreeNode*)*q2_size);
        q1_size = q2_size,q2_size = 0;
        h++;
    }
    return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

在每个树行中找最大值：LeetCode515

这个需要保存每一层的节点值吗？不用！但，我们的确还得申请一个一维数组，保存每层的最大值。每一层怎么得到最大值呢？比较大法好啊！

你确定你不试试？

在每个树行中找最大值

Code

int Height(struct TreeNode* root){
        if(!root)
            return 0;
        int h_l = Height(root->left)+1;
        int h_r = Height(root->right)+1;
        return h_l>h_r?h_l:h_r;
    } 
int* largestValues(struct TreeNode* root, int* returnSize){
    int layer = Height(root);
    *returnSize = layer;
    int* res = (int*)malloc(sizeof(int)*layer);
    struct TreeNode *q1[1000],*q2[1000];
    int q1_size = 0,q2_size = 0;
    q1[0] = root,++q1_size;

    int h = 0;
    while(h < layer){
        int max = q1[0]->val;
        for(int i = 1;i<q1_size;i++)
            if(q1[i]->val>max)
                max = q1[i]->val;
        res[h] = max;
        for(int i = 0;i<q1_size;i++){
            if(q1[i]->left)
                q2[q2_size++] = q1[i]->left;
            if(q1[i]->right)
                q2[q2_size++] = q1[i]->right;
        }
        memcpy(q1,q2,sizeof(struct TreeNode*)*q2_size);
        q1_size = q2_size,q2_size = 0;
        h++;
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

二叉树的层平均值：LeetCode637

这题自不必多说，我相信大家也会了，无非就是先求和再平均，也不用保存每层的节点值！

真的试试⑧！
二叉树的层平均值

Code

int Height(struct TreeNode* root){
    if(!root)
        return 0;
    int h_l = Height(root->left) + 1;
    int h_r = Height(root->right) + 1;
    return h_l>h_r?h_l:h_r;
}
double* averageOfLevels(struct TreeNode* root, int* returnSize){
    int layer = Height(root);
    double* res = (double*)malloc(sizeof(double)*layer);
    *returnSize = layer;
    struct TreeNode* q1[1000],*q2[1000];
    int q1_size = 1,q2_size = 0;
    q1[0] = root;
    int h  = 0;
    double sum = 0.0;
    while(h<layer){
        for(int i = 0;i<q1_size;i++)
            sum += q1[i]->val;
        res[h] = sum/q1_size;
        for(int i = 0;i<q1_size;i++){
            if(q1[i]->left)
                q2[q2_size++] = q1[i]->left;
            if(q1[i]->right)
                q2[q2_size++] = q1[i]->right;
        }
        memcpy(q1,q2,sizeof(struct TreeNode*)*q2_size);
        q1_size = q2_size,q2_size = 0;
        h++;
        sum = 0; 
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

叶子相似的树：LeetCode872

不说了，大家试试⑧
叶子相似的数

Code

class Solution {
public:
    void helper(vector<int>& leaf,TreeNode* root){
        if(!root)
            return;
        if(!root->left&&!root->right)
            leaf.push_back(root->val);
        helper(leaf,root->left);
        helper(leaf,root->right);
    }
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> leaf1;
        vector<int> leaf2;
        helper(leaf1,root1);
        helper(leaf2,root2);
        return leaf1==leaf2;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

结语

二叉树的层序遍历也可以利用队列实现
还有递归版的二叉树层序遍历（不过这个思路真的绕）
想特意练习递归的小伙伴，建议多做树的题目。

最后！做了这几个题，我直呼层序大法好！

当然，上面这几个题还有其他解法，当然不止层序遍历可以解决。