欢迎大家参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们收益!

学会二叉树的层序遍历,可以一口气打完以下十题:

  • 102.二叉树的层序遍历
  • 107.二叉树的层次遍历II
  • 199.二叉树的右视图
  • 637.二叉树的层平均值
  • 429.N叉树的前序遍历
  • 515.在每个树行中找最大值
  • 116.填充每个节点的下一个右侧节点指针
  • 117.填充每个节点的下一个右侧节点指针II
  • 104.二叉树的最大深度
  • 111.二叉树的最小深度

在之前写过这篇文章 二叉树:层序遍历登场! (opens new window),可惜当时只打了5个,还不够,再给我一次机会,我打十个!

我要打十个

# 102.二叉树的层序遍历

力扣题目链接 (opens new window)

给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。

102.二叉树的层序遍历

思路:

我们之前讲过了三篇关于二叉树的深度优先遍历的文章:

接下来我们再来介绍二叉树的另一种遍历方式:层序遍历。

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。

需要借用一个辅助数据结构即队列来实现,队列先进先出,符合一层一层遍历的逻辑,而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历,只不过我们应用在二叉树上。

使用队列实现二叉树广度优先遍历,动画如下:

102二叉树的层序遍历

这样就实现了层序从左到右遍历二叉树。

代码如下:这份代码也可以作为二叉树层序遍历的模板,打十个就靠它了

C++代码:

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

python代码:


class Solution:
    """二叉树层序遍历迭代解法"""

    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        results = []
        if not root:
            return results
        
        from collections import deque
        que = deque([root])
        
        while que:
            size = len(que)
            result = []
            for _ in range(size):
                cur = que.popleft()
                result.append(cur.val)
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
            results.append(result)

        return results
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
# 递归法
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        def helper(root, depth):
            if not root: return []
            if len(res) == depth: res.append([]) # start the current depth
            res[depth].append(root.val) # fulfil the current depth
            if  root.left: helper(root.left, depth + 1) # process child nodes for the next depth
            if  root.right: helper(root.right, depth + 1)
        helper(root, 0)
        return res
1
2
3
4
5
6
7
8
9
10
11
12

java:

// 102.二叉树的层序遍历
class Solution {
    public List<List<Integer>> resList = new ArrayList<List<Integer>>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        //checkFun01(root,0);
        checkFun02(root);

        return resList;
    }

    //DFS--递归方式
    public void checkFun01(TreeNode node, Integer deep) {
        if (node == null) return;
        deep++;

        if (resList.size() < deep) {
            //当层级增加时,list的Item也增加,利用list的索引值进行层级界定
            List<Integer> item = new ArrayList<Integer>();
            resList.add(item);
        }
        resList.get(deep - 1).add(node.val);

        checkFun01(node.left, deep);
        checkFun01(node.right, deep);
    }

    //BFS--迭代方式--借助队列
    public void checkFun02(TreeNode node) {
        if (node == null) return;
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(node);

        while (!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<Integer>();
            int len = que.size();

            while (len > 0) {
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);

                if (tmpNode.left != null) que.offer(tmpNode.left);
                if (tmpNode.right != null) que.offer(tmpNode.right);
                len--;
            }

            resList.add(itemList);
        }

    }
}
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
39
40
41
42
43
44
45
46
47
48
49
50
51

go:

/**
102. 二叉树的层序遍历
 */
func levelOrder(root *TreeNode) [][]int {
    res:=[][]int{}
    if root==nil{//防止为空
        return res
    }
    queue:=list.New()
    queue.PushBack(root)
    var tmpArr []int
    for queue.Len()>0 {
        length:=queue.Len()//保存当前层的长度,然后处理当前层(十分重要,防止添加下层元素影响判断层中元素的个数)
        for i:=0;i<length;i++{
            node:=queue.Remove(queue.Front()).(*TreeNode)//出队列
            if node.Left!=nil{
                queue.PushBack(node.Left)
            }
            if node.Right!=nil{
                queue.PushBack(node.Right)
            }
            tmpArr=append(tmpArr,node.Val)//将值加入本层切片中
        }
        res=append(res,tmpArr)//放入结果集
        tmpArr=[]int{}//清空层的数据
    }
    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

javascript代码:

var levelOrder = function(root) {
    //二叉树的层序遍历
    let res=[],queue=[];
    queue.push(root);
    if(root===null){
        return res;
    }
    while(queue.length!==0){
        // 记录当前层级节点数
        let length=queue.length;
        //存放每一层的节点 
        let curLevel=[];
        for(let i=0;i<length;i++){
            let node=queue.shift();
            curLevel.push(node.val);
            // 存放当前层下一层的节点
            node.left&&queue.push(node.left);
            node.right&&queue.push(node.right);
        }
        //把每一层的结果放到结果数组
        res.push(curLevel);
    }
    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

此时我们就掌握了二叉树的层序遍历了,那么如下九道力扣上的题目,只需要修改模板的两三行代码(不能再多了),便可打倒!

# 107.二叉树的层次遍历 II

力扣题目链接 (opens new window)

给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

107.二叉树的层次遍历II

思路:

相对于102.二叉树的层序遍历,就是最后把result数组反转一下就可以了。

C++代码:

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        reverse(result.begin(), result.end()); // 在这里反转一下数组即可
        return result;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

python代码:

class Solution:
    """二叉树层序遍历II迭代解法"""

    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        results = []
        if not root:
            return results
        
        from collections import deque
        que = deque([root])
        
        while que:
            result = []
            for _ in range(len(que)):
                cur = que.popleft()
                result.append(cur.val)
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
            results.append(result)

        results.reverse()
        return results
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Java:

// 107. 二叉树的层序遍历 II
public class N0107 {

    /**
     * 解法:队列,迭代。
     * 层序遍历,再翻转数组即可。
     */
    public List<List<Integer>> solution1(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        Deque<TreeNode> que = new LinkedList<>();

        if (root == null) {
            return list;
        }

        que.offerLast(root);
        while (!que.isEmpty()) {
            List<Integer> levelList = new ArrayList<>();

            int levelSize = que.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode peek = que.peekFirst();
                levelList.add(que.pollFirst().val);

                if (peek.left != null) {
                    que.offerLast(peek.left);
                }
                if (peek.right != null) {
                    que.offerLast(peek.right);
                }
            }
            list.add(levelList);
        }

        List<List<Integer>> result = new ArrayList<>();
        for (int i = list.size() - 1; i >= 0; i-- ) {
            result.add(list.get(i));
        }

        return result;
    }
}
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
39
40
41
42

go:

/**
107. 二叉树的层序遍历 II
 */
func levelOrderBottom(root *TreeNode) [][]int {
    queue:=list.New()
    res:=[][]int{}
    if root==nil{
        return res
    }
    queue.PushBack(root)
    for queue.Len()>0{
        length:=queue.Len()
        tmp:=[]int{}
        for i:=0;i<length;i++{
            node:=queue.Remove(queue.Front()).(*TreeNode)
            if node.Left!=nil{
                queue.PushBack(node.Left)
            }
            if node.Right!=nil{
                queue.PushBack(node.Right)
            }
            tmp=append(tmp,node.Val)
        }
        res=append(res,tmp)
    }
    //反转结果集
    for i:=0;i<len(res)/2;i++{
        res[i],res[len(res)-i-1]=res[len(res)-i-1],res[i]
    }
    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

javascript代码

var levelOrderBottom = function(root) {
    let res=[],queue=[];
    queue.push(root);
    while(queue.length&&root!==null){
        // 存放当前层级节点数组
        let curLevel=[];
        // 计算当前层级节点数量
        let length=queue.length;
        while(length--){
            let node=queue.shift();
            // 把当前层节点存入curLevel数组
            curLevel.push(node.val);
            // 把下一层级的左右节点存入queue队列
            node.left&&queue.push(node.left);
            node.right&&queue.push(node.right);
        }
        res.push(curLevel);
    }
    return res.reverse();
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 199.二叉树的右视图

力扣题目链接 (opens new window)

给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

199.二叉树的右视图

思路:

层序遍历的时候,判断是否遍历到单层的最后面的元素,如果是,就放进result数组中,随后返回result就可以了。

C++代码:

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<int> result;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (i == (size - 1)) result.push_back(node->val); // 将每一层的最后元素放入result数组中
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

python代码:

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        
        # deque来自collections模块,不在力扣平台时,需要手动写入
        # 'from collections import deque' 导入
        # deque相比list的好处是,list的pop(0)是O(n)复杂度,deque的popleft()是O(1)复杂度

        quene = deque([root])
        out_list = []

        while quene:
            # 每次都取最后一个node就可以了
            node = quene[-1]
            out_list.append(node.val)

            # 执行这个遍历的目的是获取下一层所有的node
            for _ in range(len(quene)):
                node = quene.popleft()
                if node.left:
                    quene.append(node.left)
                if node.right:
                    quene.append(node.right)
        
        return out_list
    
# 执行用时:36 ms, 在所有 Python3 提交中击败了89.47%的用户
# 内存消耗:14.6 MB, 在所有 Python3 提交中击败了96.65%的用户
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

Java:

// 199.二叉树的右视图
public class N0199 {
    /**
     * 解法:队列,迭代。
     * 每次返回每层的最后一个字段即可。
     *
     * 小优化:每层右孩子先入队。代码略。
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> que = new LinkedList<>();

        if (root == null) {
            return list;
        }

        que.offerLast(root);
        while (!que.isEmpty()) {
            int levelSize = que.size();

            for (int i = 0; i < levelSize; i++) {
                TreeNode poll = que.pollFirst();

                if (poll.left != null) {
                    que.addLast(poll.left);
                }
                if (poll.right != null) {
                    que.addLast(poll.right);
                }

                if (i == levelSize - 1) {
                    list.add(poll.val);
                }
            }
        }

        return list;
    }
}
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
39

go:


/**
199. 二叉树的右视图
 */
func rightSideView(root *TreeNode) []int {
    queue:=list.New()
    res:=[][]int{}
    var finaRes []int
    if root==nil{
        return finaRes
    }
    queue.PushBack(root)
    for queue.Len()>0{
        length:=queue.Len()
        tmp:=[]int{}
        for i:=0;i<length;i++{
            node:=queue.Remove(queue.Front()).(*TreeNode)
            if node.Left!=nil{
                queue.PushBack(node.Left)
            }
            if node.Right!=nil{
                queue.PushBack(node.Right)
            }
            tmp=append(tmp,node.Val)
        }
        res=append(res,tmp)
    }
    //取每一层的最后一个元素
    for i:=0;i<len(res);i++{
        finaRes=append(finaRes,res[i][len(res[i])-1])
    }
    return finaRes
}
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

javascript代码:

var rightSideView = function(root) {
    //二叉树右视图 只需要把每一层最后一个节点存储到res数组
    let res=[],queue=[];
    queue.push(root);
    while(queue.length&&root!==null){
        // 记录当前层级节点个数
        let length=queue.length;
        while(length--){
            let node=queue.shift();
            //length长度为0的时候表明到了层级最后一个节点
            if(!length){
                res.push(node.val);
            }
            node.left&&queue.push(node.left);
            node.right&&queue.push(node.right);
        }
    }
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 637.二叉树的层平均值

力扣题目链接 (opens new window)

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

637.二叉树的层平均值

思路:

本题就是层序遍历的时候把一层求个总和在取一个均值。

C++代码:

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<double> result;
        while (!que.empty()) {
            int size = que.size();
            double sum = 0; // 统计每一层的和
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                sum += node->val;
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(sum / size); // 将每一层均值放进结果集
        }
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

python代码:

class Solution:
    """二叉树层平均值迭代解法"""

    def averageOfLevels(self, root: TreeNode) -> List[float]:
        results = []
        if not root:
            return results
        
        from collections import deque
        que = deque([root])
        
        while que:
            size = len(que)
            sum_ = 0
            for _ in range(size):
                cur = que.popleft()
                sum_ += cur.val
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
            results.append(sum_ / size)

        return results
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

java:


// 637. 二叉树的层平均值
public class N0637 {

    /**
     * 解法:队列,迭代。
     * 每次返回每层的最后一个字段即可。
     */
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> list = new ArrayList<>();
        Deque<TreeNode> que = new LinkedList<>();

        if (root == null) {
            return list;
        }

        que.offerLast(root);
        while (!que.isEmpty()) {
            TreeNode peek = que.peekFirst();

            int levelSize = que.size();
            double levelSum = 0.0;
            for (int i = 0; i < levelSize; i++) {
                TreeNode poll = que.pollFirst();

                levelSum += poll.val;

                if (poll.left != null) {
                    que.addLast(poll.left);
                }
                if (poll.right != null) {
                    que.addLast(poll.right);
                }
            }
            list.add(levelSum / levelSize);
        }
        return list;
    }
}
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
39

go:

/**
637. 二叉树的层平均值
 */
func averageOfLevels(root *TreeNode) []float64 {
    res:=[][]int{}
    var finRes []float64
    if root==nil{//防止为空
        return finRes
    }
    queue:=list.New()
    queue.PushBack(root)
    var tmpArr []int
    for queue.Len()>0 {
        length:=queue.Len()//保存当前层的长度,然后处理当前层(十分重要,防止添加下层元素影响判断层中元素的个数)
        for i:=0;i<length;i++{
            node:=queue.Remove(queue.Front()).(*TreeNode)//出队列
            if node.Left!=nil{
                queue.PushBack(node.Left)
            }
            if node.Right!=nil{
                queue.PushBack(node.Right)
            }
            tmpArr=append(tmpArr,node.Val)//将值加入本层切片中
        }
        res=append(res,tmpArr)//放入结果集
        tmpArr=[]int{}//清空层的数据
    }
    //计算每层的平均值
    length:=len(res)
    for i:=0;i<length;i++{
        var sum int
        for j:=0;j<len(res[i]);j++{
            sum+=res[i][j]
        }
        tmp:=float64(sum)/float64(len(res[i]))
        finRes=append(finRes,tmp)//将平均值放入结果集合
    }
    return finRes
}
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
39

javascript代码:

var averageOfLevels = function(root) {
    //层级平均值
    let res=[],queue=[];
    queue.push(root);
    while(queue.length&&root!==null){
        //每一层节点个数
        let length=queue.length;
        //sum记录每一层的和
        let sum=0;
        for(let i=0;i<length;i++){
            let node=queue.shift();
            sum+=node.val;
            node.left&&queue.push(node.left);
            node.right&&queue.push(node.right);
        }
        //每一层的平均值存入数组res
        res.push(sum/length);
    }
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 429.N叉树的层序遍历

力扣题目链接 (opens new window)

给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。

例如,给定一个 3叉树 :

429. N叉树的层序遍历

返回其层序遍历:

[ [1], [3,2,4], [5,6] ]

思路:

这道题依旧是模板题,只不过一个节点有多个孩子了

C++代码:

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            for (int i = 0; i < size; i++) {
                Node* node = que.front();
                que.pop();
                vec.push_back(node->val);
                for (int i = 0; i < node->children.size(); i++) { // 将节点孩子加入队列
                    if (node->children[i]) que.push(node->children[i]);
                }
            }
            result.push_back(vec);
        }
        return result;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

python代码:

class Solution:
    """N叉树的层序遍历迭代法"""

    def levelOrder(self, root: 'Node') -> List[List[int]]:
        results = []
        if not root:
            return results
        
        from collections import deque
        que = deque([root])
        
        while que:
            result = []
            for _ in range(len(que)):
                cur = que.popleft()
                result.append(cur.val)
                # cur.children 是 Node 对象组成的列表,也可能为 None
                if cur.children:
                    que.extend(cur.children)
            results.append(result)

        return results
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

java:


// 429. N 叉树的层序遍历
public class N0429 {
    /**
     * 解法1:队列,迭代。
     */
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> list = new ArrayList<>();
        Deque<Node> que = new LinkedList<>();

        if (root == null) {
            return list;
        }

        que.offerLast(root);
        while (!que.isEmpty()) {
            int levelSize = que.size();
            List<Integer> levelList = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                Node poll = que.pollFirst();

                levelList.add(poll.val);

                List<Node> children = poll.children;
                if (children == null || children.size() == 0) {
                    continue;
                }
                for (Node child : children) {
                    if (child != null) {
                        que.offerLast(child);
                    }
                }
            }
            list.add(levelList);
        }

        return list;
    }

    class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }
}
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

go:

/**
429. N 叉树的层序遍历
 */

func levelOrder(root *Node) [][]int {
    queue:=list.New()
    res:=[][]int{}//结果集
    if root==nil{
        return res
    }
    queue.PushBack(root)
    for queue.Len()>0{
        length:=queue.Len()//记录当前层的数量
        var tmp []int
        for T:=0;T<length;T++{//该层的每个元素:一添加到该层的结果集中;二找到该元素的下层元素加入到队列中,方便下次使用
            myNode:=queue.Remove(queue.Front()).(*Node)
            tmp=append(tmp,myNode.Val)
            for i:=0;i<len(myNode.Children);i++{
                queue.PushBack(myNode.Children[i])
            }
        }
        res=append(res,tmp)
    }
    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

JavaScript代码:

var levelOrder = function(root) {
    //每一层可能有2个以上,所以不再使用node.left node.right
    let res=[],queue=[];
    queue.push(root);
    while(queue.length&&root!==null){
        //记录每一层节点个数还是和二叉树一致
        let length=queue.length;
        //存放每层节点 也和二叉树一致
        let curLevel=[];
        while(length--){
            let node = queue.shift();
            curLevel.push(node.val);
            //这里不再是 ndoe.left node.right 而是循坏node.children
           for(let item of node.children){
               item&&queue.push(item);
           }
        }
        res.push(curLevel);
    }
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

力扣题目链接 (opens new window)

您需要在二叉树的每一行中找到最大的值。

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

思路:

层序遍历,取每一层的最大值

C++代码:

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<int> result;
        while (!que.empty()) {
            int size = que.size();
            int maxValue = INT_MIN; // 取每一层的最大值
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                maxValue = node->val > maxValue ? node->val : maxValue;
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(maxValue); // 把最大值放进数组
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

python代码:

class Solution:
    def largestValues(self, root: TreeNode) -> List[int]:
        if root is None:
            return []
        queue = [root]
        out_list = []
        while queue:
            length = len(queue)
            in_list = []
            for _ in range(length):
                curnode = queue.pop(0)
                in_list.append(curnode.val)
                if curnode.left: queue.append(curnode.left)
                if curnode.right: queue.append(curnode.right)
            out_list.append(max(in_list))
        return out_list
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

java代码:

class Solution {
    public List<Integer> largestValues(TreeNode root) {
		List<Integer> retVal = new ArrayList<Integer>();
		Queue<TreeNode> tmpQueue = new LinkedList<TreeNode>();
		if (root != null) tmpQueue.add(root);
		
		while (tmpQueue.size() != 0){
			int size = tmpQueue.size();
			List<Integer> lvlVals = new ArrayList<Integer>();
			for (int index = 0; index < size; index++){
				TreeNode node = tmpQueue.poll();
				lvlVals.add(node.val);
				if (node.left != null) tmpQueue.add(node.left);
				if (node.right != null) tmpQueue.add(node.right);
			}
			retVal.add(Collections.max(lvlVals));
		}
        
        return retVal;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

go:

/**
515. 在每个树行中找最大值
 */
func largestValues(root *TreeNode) []int {
    res:=[][]int{}
    var finRes []int
    if root==nil{//防止为空
        return finRes
    }
    queue:=list.New()
    queue.PushBack(root)
    var tmpArr []int
    //层次遍历
    for queue.Len()>0 {
        length:=queue.Len()//保存当前层的长度,然后处理当前层(十分重要,防止添加下层元素影响判断层中元素的个数)
        for i:=0;i<length;i++{
            node:=queue.Remove(queue.Front()).(*TreeNode)//出队列
            if node.Left!=nil{
                queue.PushBack(node.Left)
            }
            if node.Right!=nil{
                queue.PushBack(node.Right)
            }
            tmpArr=append(tmpArr,node.Val)//将值加入本层切片中
        }
        res=append(res,tmpArr)//放入结果集
        tmpArr=[]int{}//清空层的数据
    }
    //找到每层的最大值
    for i:=0;i<len(res);i++{
        finRes=append(finRes,max(res[i]...))
    }
    return finRes
}
func max(vals...int) int {
    max:=int(math.Inf(-1))//负无穷
    for _, val := range vals {
        if val > max {
            max = val
        }
    }
    return max
}
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
39
40
41
42
43

javascript代码:

var largestValues = function(root) {
    //使用层序遍历
    let res=[],queue=[];
    queue.push(root);
    while(root!==null&&queue.length){
        //设置max初始值就是队列的第一个元素
        let max=queue[0].val;
        let length=queue.length;
        while(length--){
            let node = queue.shift();
            max=max>node.val?max:node.val;
            node.left&&queue.push(node.left);
            node.right&&queue.push(node.right);
        }
        //把每一层的最大值放到res数组
        res.push(max);
    }
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

力扣题目链接 (opens new window)

给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
1
2
3
4
5
6

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

初始状态下,所有 next 指针都被设置为 NULL。

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

思路:

本题依然是层序遍历,只不过在单层遍历的时候记录一下本层的头部节点,然后在遍历的时候让前一个节点指向本节点就可以了

C++代码:

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            Node* nodePre;
            Node* node;
            for (int i = 0; i < size; i++) {
                if (i == 0) {
                    nodePre = que.front(); // 取出一层的头结点
                    que.pop();
                    node = nodePre;
                } else {
                    node = que.front();
                    que.pop();
                    nodePre->next = node; // 本层前一个节点next指向本节点
                    nodePre = nodePre->next;
                }
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            nodePre->next = NULL; // 本层最后一个节点指向NULL
        }
        return root;

    }
};
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

java代码:

class Solution {
    public Node connect(Node root) {
	Queue<Node> tmpQueue = new LinkedList<Node>();
	if (root != null) tmpQueue.add(root);
		
	while (tmpQueue.size() != 0){
	    int size = tmpQueue.size();
            
            Node cur = tmpQueue.poll();
            if (cur.left != null) tmpQueue.add(cur.left);
            if (cur.right != null) tmpQueue.add(cur.right);
            
	    for (int index = 1; index < size; index++){
		Node next = tmpQueue.poll();
		if (next.left != null) tmpQueue.add(next.left);
		if (next.right != null) tmpQueue.add(next.right);
                
                cur.next = next;
                cur = next;
	    }
	}
        
        return root;
    }
}
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

python代码:

# 层序遍历解法
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None
        queue = [root]
        while queue:
            n = len(queue)
            for i in range(n):
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                if i == n - 1:
                    break
                node.next = queue[0]
        return root

# 链表解法
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        first = root
        while first:
            cur = first
            while cur:  # 遍历每一层的节点
                if cur.left: cur.left.next = cur.right  # 找左节点的next
                if cur.right and cur.next: cur.right.next = cur.next.left  # 找右节点的next
                cur = cur.next # cur同层移动到下一节点
            first = first.left  # 从本层扩展到下一层
        return root
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

go:

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

func connect(root *Node) *Node {
   res:=[][]*Node{}
    if root==nil{//防止为空
        return root
    }
    queue:=list.New()
    queue.PushBack(root)
    var tmpArr []*Node
    for queue.Len()>0 {
        length:=queue.Len()//保存当前层的长度,然后处理当前层(十分重要,防止添加下层元素影响判断层中元素的个数)
        for i:=0;i<length;i++{
            node:=queue.Remove(queue.Front()).(*Node)//出队列
            if node.Left!=nil{
                queue.PushBack(node.Left)
            }
            if node.Right!=nil{
                queue.PushBack(node.Right)
            }
            tmpArr=append(tmpArr,node)//将值加入本层切片中
        }
        res=append(res,tmpArr)//放入结果集
        tmpArr=[]*Node{}//清空层的数据
    }
    //遍历每层元素,指定next
    for i:=0;i<len(res);i++{
        for j:=0;j<len(res[i])-1;j++{
            res[i][j].Next=res[i][j+1]
        }
    }
    return root
}
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

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

力扣题目链接 (opens new window)

思路:

这道题目说是二叉树,但116题目说是完整二叉树,其实没有任何差别,一样的代码一样的逻辑一样的味道

C++代码:

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            Node* nodePre;
            Node* node;
            for (int i = 0; i < size; i++) {
                if (i == 0) {
                    nodePre = que.front(); // 取出一层的头结点
                    que.pop();
                    node = nodePre;
                } else {
                    node = que.front();
                    que.pop();
                    nodePre->next = node; // 本层前一个节点next指向本节点
                    nodePre = nodePre->next;
                }
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            nodePre->next = NULL; // 本层最后一个节点指向NULL
        }
        return root;
    }
};
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

Java 代码:

// 二叉树之层次遍历
class Solution {
    public Node connect(Node root) {
        Queue<Node> queue = new LinkedList<>();
        if (root != null) {
            queue.add(root);
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            Node node = null;
            Node nodePre = null;
 
            for (int i = 0; i < size; i++) {
                if (i == 0) {
                    nodePre = queue.poll(); // 取出本层头一个节点
                    node = nodePre;
                } else {
                    node = queue.poll();
                    nodePre.next = node; // 本层前一个节点 next 指向当前节点
                    nodePre = nodePre.next;
                }
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            nodePre.next = null; // 本层最后一个节点 next 指向 null
        }
        return root;
    }
}
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

python代码:

# 层序遍历解法
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None
        queue = [root]
        while queue:  # 遍历每一层
            length = len(queue)
            tail = None # 每一层维护一个尾节点
            for i in range(length): # 遍历当前层
                curnode = queue.pop(0)
                if tail:
                    tail.next = curnode # 让尾节点指向当前节点
                tail = curnode # 让当前节点成为尾节点
                if curnode.left : queue.append(curnode.left)
                if curnode.right: queue.append(curnode.right)
        return root

# 链表解法
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None
        first = root
        while first:  # 遍历每一层
            dummyHead = Node(None)  # 为下一行创建一个虚拟头节点,相当于下一行所有节点链表的头结点(每一层都会创建);
            tail = dummyHead  # 为下一行维护一个尾节点指针(初始化是虚拟节点)
            cur = first
            while cur:  # 遍历当前层的节点
                if cur.left:  # 链接下一行的节点
                    tail.next = cur.left
                    tail = tail.next
                if cur.right:
                    tail.next = cur.right
                    tail = tail.next
                cur = cur.next  # cur同层移动到下一节点
            first = dummyHead.next  # 此处为换行操作,更新到下一行
        return root
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

go:

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

func connect(root *Node) *Node {
   res:=[][]*Node{}
    if root==nil{//防止为空
        return root
    }
    queue:=list.New()
    queue.PushBack(root)
    var tmpArr []*Node
    for queue.Len()>0 {
        length:=queue.Len()//保存当前层的长度,然后处理当前层(十分重要,防止添加下层元素影响判断层中元素的个数)
        for i:=0;i<length;i++{
            node:=queue.Remove(queue.Front()).(*Node)//出队列
            if node.Left!=nil{
                queue.PushBack(node.Left)
            }
            if node.Right!=nil{
                queue.PushBack(node.Right)
            }
            tmpArr=append(tmpArr,node)//将值加入本层切片中
        }
        res=append(res,tmpArr)//放入结果集
        tmpArr=[]*Node{}//清空层的数据
    }
    //遍历每层元素,指定next
    for i:=0;i<len(res);i++{
        for j:=0;j<len(res[i])-1;j++{
            res[i][j].Next=res[i][j+1]
        }
    }
    return root
}
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

# 104.二叉树的最大深度

力扣题目链接 (opens new window)

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

104. 二叉树的最大深度

返回它的最大深度 3 。

思路:

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

在二叉树中,一层一层的来遍历二叉树,记录一下遍历的层数就是二叉树的深度,如图所示:

层序遍历

所以这道题的迭代法就是一道模板题,可以使用二叉树层序遍历的模板来解决的。

C++代码如下:

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int depth = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            depth++; // 记录深度
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return depth;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Java:

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null)   return 0;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        int depth = 0;
        while (!que.isEmpty())
        {
            int len = que.size();
            while (len > 0)
            {
                TreeNode node = que.poll();
                if (node.left != null)  que.offer(node.left);
                if (node.right != null) que.offer(node.right);
                len--;
            }
            depth++;
        }
        return depth;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Python:

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root == None:
            return 0
        
        queue_ = [root]
        result = []
        while queue_:
            length = len(queue_)
            sub = []
            for i in range(length):
                cur = queue_.pop(0)
                sub.append(cur.val)
                #子节点入队列
                if cur.left: queue_.append(cur.left)
                if cur.right: queue_.append(cur.right)
            result.append(sub)
            

        return len(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Go:

JavaScript:

# 111.二叉树的最小深度

力扣题目链接 (opens new window)

相对于 104.二叉树的最大深度 ,本题还也可以使用层序遍历的方式来解决,思路是一样的。

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

代码如下:(详细注释)

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int depth = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            depth++; // 记录最小深度
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                if (!node->left && !node->right) { // 当左右孩子都为空的时候,说明是最低点的一层了,退出
                    return depth;
                }
            }
        }
        return depth;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Java:

class Solution {
    public int minDepth(TreeNode root){
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            depth++;
            TreeNode cur = null;
            for (int i = 0; i < size; i++) {
                cur = queue.poll();
                //如果当前节点的左右孩子都为空,直接返回最小深度
                if (cur.left == null && cur.right == null){
                    return depth;
                }
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
        }
        return depth;
    }
}
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

Python 3:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if root == None:
            return 0

        #根节点的深度为1
        queue_ = [(root,1)]
        while queue_:
            cur, depth = queue_.pop(0)
            
            if cur.left == None and cur.right == None:
                return depth
            #先左子节点,由于左子节点没有孩子,则就是这一层了
            if cur.left:
                queue_.append((cur.left,depth + 1))
            if cur.right:
                queue_.append((cur.right,depth + 1))

        return 0
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

Go:

JavaScript:

# 总结

二叉树的层序遍历,就是图论中的广度优先搜索在二叉树中的应用,需要借助队列来实现(此时又发现队列的一个应用了)。

来吧,一口气打十个:

  • 102.二叉树的层序遍历
  • 107.二叉树的层次遍历II
  • 199.二叉树的右视图
  • 637.二叉树的层平均值
  • 429.N叉树的前序遍历
  • 515.在每个树行中找最大值
  • 116.填充每个节点的下一个右侧节点指针
  • 117.填充每个节点的下一个右侧节点指针II
  • 104.二叉树的最大深度
  • 111.二叉树的最小深度

致敬叶师傅!