南宁良庆网站建设,wordpress ie,phpcms二级栏目文章列表调用网站最新文章的方法,wordpress文章无法使用【算法系列-二叉树】层序遍历 文章目录 【算法系列-二叉树】层序遍历1. 算法分析#x1f6f8;2. 相似题型#x1f3af;2.1 二叉树的层序遍历II(LeetCode 107)2.2 二叉树的右视图(LeetCode 199)2.3 二叉树的层平均值(LeetCode 637)2.4 N叉树的层序遍历(LeetCode 429)2.5 在每个…【算法系列-二叉树】层序遍历 文章目录 【算法系列-二叉树】层序遍历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 ListListInteger levelOrder(TreeNode root) {ListListInteger ret new ArrayList();if (root null) {return ret;}QueueTreeNode queue new LinkedList();queue.offer(root);while (!queue.isEmpty()) {ListInteger 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 ListListInteger levelOrderBottom(TreeNode root) {ListListInteger ret new ArrayList();if (root null) {return ret;}QueueTreeNode queue new LinkedList();queue.offer(root);while (!queue.isEmpty()) {ListInteger 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 ListInteger rightSideView(TreeNode root) {ListInteger ret new ArrayList();if (root null) {return ret;}QueueTreeNode 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(QueueTreeNode 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 ListDouble averageOfLevels(TreeNode root) {ListDouble ret new ArrayList();if (root null) {return ret;}QueueTreeNode 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 ListNode children;public Node() {}public Node(int _val) {val _val;}public Node(int _val, ListNode _children) {val _val;children _children;}
};
*/class Solution {public ListListInteger levelOrder(Node root) {ListListInteger ret new ArrayList();if (root null) {return ret;}QueueNode queue new LinkedList();queue.offer(root);while (!queue.isEmpty()) {ListInteger list new ArrayList();int size queue.size();while (size 0) {Node cur queue.poll();list.add(cur.val);ListNode 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 ListInteger largestValues(TreeNode root) {ListInteger ret new ArrayList();if (root null) {return ret;}QueueTreeNode 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;}QueueNode 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;}QueueTreeNode 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;}QueueTreeNode 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;}
}以上便是对二叉树层序遍历问题的介绍了后续还会继续分享其它算法系列内容如果这些内容对大家有帮助的话请给一个三连关注吧( •̀ ω •́ )✧( •̀ ω •́ )✧✨
