前言

算法是计算机软件的根底,常见算法是软件开发的核心基本功,今年打算深入学习一些算法,记载一些算法理论以及最佳实践,期望能够坚持下去,重视我,咱们一同学习,增强咱们的基本功。

本文内容是层序遍历二叉树,学会了层序遍历的方法,leetcode上的10道标题都能够轻松解决,真的无敌啊。

102. 二叉树的层序遍历

104. 二叉树的最大深度

107. 二叉树的层序遍历 II

111. 二叉树的最小深度

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

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

199. 二叉树的右视图

429. N 叉树的层序遍历

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

637. 二叉树的层平均值

二叉树进阶-学会层序遍历助你一次刷完leetcode10道题

一、层序遍历概述

层序遍历是一层一层的遍历二叉树。因为递归遍历是一种深度查找的方法,因而递归遍历在这里是行不通的。

二叉树进阶-学会层序遍历助你一次刷完leetcode10道题

10

6 16

1 8 12 19

咱们能够发现下一层,在上一层遍历完成之后就能够确认了,因为咱们遍历一层的时分,把子节点记载下来就能够。因而咱们在遍历当时层的时分能够把下一层的节点存储起来。为了确保是从左到右次序按层遍历元素,咱们运用行列这种数据结构来存储。

比方上图的树

首先咱们把根节点参加行列,这时行列里存储了第一层的数据,咱们开端遍历行列里的第一层根节点10;遍历一起一起把左右节点6,16存储起来。

遍历完第一层,这时开端遍历第二层,循环行列里面两个元素,咱们能够得到第三层的节点并存储到行列中。

二、层序遍历实战

leetcode102. 二叉树的层序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null) {
            return result;
        }
        List<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            //下一层的巨细,
           int size =  queue.size();
           List<Integer> raw = new ArrayList<>();
           //遍历某一层
           for(int i=0; i<size; i++) {
              TreeNode node =  queue.removeFirst();
              raw.add(node.val);
              if(node.left != null) {
                  queue.add(node.left);
              }
              if(node.right != null) {
                  queue.add(node.right);
              }
           }
           //记载一层的数据
           result.add(raw);
        }
        return result;
    }
}

三、总结

层序遍历是一种广度优先查找的遍历方法,把握一层一层遍历二叉树的方法,真的能够解决文字最初说的10道题。

102. 二叉树的层序遍历

104. 二叉树的最大深度

107. 二叉树的层序遍历 II

111. 二叉树的最小深度

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

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

199. 二叉树的右视图

429. N 叉树的层序遍历

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

637. 二叉树的层平均值