【算法系列-二叉树】层序遍历

文章目录

【算法系列-二叉树】层序遍历
- 1. 算法分析🛸
- 2. 相似题型🎯
- - 2.1 二叉树的层序遍历II(LeetCode 107)
  - 2.2 二叉树的右视图(LeetCode 199)
  - 2.3 二叉树的层平均值(LeetCode 637)
  - 2.4 N叉树的层序遍历(LeetCode 429)
  - 2.5 在每个树行中找最大值(LeetCode 515)
  - 2.6 填充每个节点的下一个右侧节点指针(LeetCode 116)
  - 2.7 二叉树的最大深度(LeetCode 104)
  - 2.8 二叉树的最小深度(LeetCode 111)

1. 算法分析🛸

二叉树的层序遍历就是对树进行广度优先搜索，一层一层的对树的节点进行遍历；

【题目链接】102. 二叉树的层序遍历 - 力扣（LeetCode）

在这里，我们通过队列来辅助实现二叉树的层序遍历，关键在于寻找到判断当前节点正在哪一层且这一层的节点是否遍历完的条件。

解题过程🎬

定义一个size，这个size等于当前队列的长度大小；

开始先将根节点加入队列，形成第一层；此时size = 1，再将队列中的节点弹出，将该节点的左右节点加入队列(非空)，同时size - 1；

重复上述过程，直到size = 0时，表示当前层数的节点已经遍历完，进入下一层，直到队列为空，返回结果

代码示例🌰

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ret = new ArrayList<>();if (root == null) {return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {List<Integer> list = new ArrayList<>();int size = queue.size();while (size > 0) {TreeNode cur = queue.poll();list.add(cur.val);if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}size--;}ret.add(list);}return ret;}
}

下面提供一些与层序遍历解法相似的类型题:

2. 相似题型🎯

2.1 二叉树的层序遍历II(LeetCode 107)

【题目链接】107. 二叉树的层序遍历 II - 力扣（LeetCode）

代码示例🌰

class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> ret = new ArrayList<>();if (root == null) {return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {List<Integer> list = new ArrayList<>();int size = queue.size();while (size > 0) {TreeNode cur = queue.poll();list.add(cur.val);if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}size--;}ret.add(0, list);}return ret;}
}

2.2 二叉树的右视图(LeetCode 199)

【题目链接】199. 二叉树的右视图 - 力扣（LeetCode）

解题思路与使用队列的层序遍历相同，需要注意的是要找到能够在右视图看到的节点，这个节点可以是左节点也可以是右节点，但它一定是每一层遍历的最右边节点，对此在遍历到队列中size为0的前一个节点时，将这个节点的值加入返回数组即可

代码示例🌰

class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> ret = new ArrayList<>();if (root == null) {return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();while (size > 1) {queueOfferNode(queue);size--;}TreeNode node = queueOfferNode(queue);ret.add(node.val);}return ret;}TreeNode queueOfferNode(Queue<TreeNode> queue) {TreeNode cur = queue.poll();if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}return cur;}
}

2.3 二叉树的层平均值(LeetCode 637)

【题目链接】637. 二叉树的层平均值 - 力扣（LeetCode）

代码示例🌰

class Solution {public List<Double> averageOfLevels(TreeNode root) {List<Double> ret = new ArrayList<>();if (root == null) {return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();int num = size;double sum = 0;while (size > 0) {TreeNode cur = queue.poll();sum += cur.val;if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}size--;}ret.add(sum / num);}return ret;}
}

2.4 N叉树的层序遍历(LeetCode 429)

【题目链接】429. N 叉树的层序遍历 - 力扣（LeetCode）

代码示例🌰

/*
// Definition for a Node.
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;}
};
*/class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> ret = new ArrayList<>();if (root == null) {return ret;}Queue<Node> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {List<Integer> list = new ArrayList<>();int size = queue.size();while (size > 0) {Node cur = queue.poll();list.add(cur.val);List<Node> children = cur.children;for (Node node : children) {if (node != null) {queue.offer(node);}}size--;}ret.add(list);}return ret;}
}

2.5 在每个树行中找最大值(LeetCode 515)

【题目链接】515. 在每个树行中找最大值 - 力扣（LeetCode）

代码示例🌰

class Solution {public List<Integer> largestValues(TreeNode root) {List<Integer> ret = new ArrayList<>();if (root == null) {return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();int max = Integer.MIN_VALUE;while (size > 0) {TreeNode cur = queue.poll();if (cur.val > max) {max = cur.val;}if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}size--;}ret.add(max);}return ret;}
}

2.6 填充每个节点的下一个右侧节点指针(LeetCode 116)

【题目链接】116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）

代码示例🌰

/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, Node _left, Node _right, Node _next) {val = _val;left = _left;right = _right;next = _next;}
};
*/class Solution {public Node connect(Node root) {if (root == null) {return root;}Queue<Node> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();while (size-- > 0) {Node cur1 = queue.poll();Node cur2 = size == 0 ? null : queue.peek();cur1.next = cur2;if (cur1.left != null) {queue.offer(cur1.left);}if (cur1.right != null) {queue.offer(cur1.right);}}}return root;}
}

2.7 二叉树的最大深度(LeetCode 104)

【题目链接】104. 二叉树的最大深度 - 力扣（LeetCode）

代码示例🌰

class Solution {public int maxDepth(TreeNode root) {int ret = 0;if (root == null) {return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {ret++;int size = queue.size();while (size > 0) {TreeNode cur = queue.poll();if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}size--;}}return ret;}
}

2.8 二叉树的最小深度(LeetCode 111)

【题目链接】111. 二叉树的最小深度 - 力扣（LeetCode）

代码示例🌰

class Solution {public int minDepth(TreeNode root) {int ret = 0;if (root == null) {return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {ret++;int size = queue.size();while (size > 0) {TreeNode cur = queue.poll();if (cur.left == null && cur.right == null) {return ret;}if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}size--;}}return ret;}
}