网站备案账户名如何查询,网站建设推荐华网天下,扬州网官方微博,wordpress 单栏模板好的#xff0c;我来用中文详细解释这段代码的算法思想。
问题描述
题目要求给定一个二叉树的根节点#xff0c;从树的右侧看过去#xff0c;按从上到下的顺序返回看到的节点值。即#xff0c;我们需要找到每一层的最右侧节点并将其加入结果中。
算法思想
这道题可以通… 好的我来用中文详细解释这段代码的算法思想。
问题描述
题目要求给定一个二叉树的根节点从树的右侧看过去按从上到下的顺序返回看到的节点值。即我们需要找到每一层的最右侧节点并将其加入结果中。
算法思想
这道题可以通过广度优先搜索BFS来解决。BFS的特点是逐层遍历树的节点非常适合在每一层获取最右侧的节点。以下是具体的算法步骤 使用队列进行层序遍历 我们采用BFS来逐层遍历树BFS通常会使用队列Queue来实现。首先将树的根节点放入队列中。 每层节点的遍历 在每一层开始时我们记录队列的大小即当前层的节点数。然后我们依次从队列中取出该层的每一个节点处理这些节点并将它们的左右子节点加入队列以便下一层继续遍历。在遍历当前层的节点时我们将当前层的最后一个节点即最右侧的节点保存下来。 记录每层最右侧的节点 对于每一层的节点最后一个处理的节点就是该层的最右侧节点。因此在遍历每层的过程中我们将每层最后一个节点的值添加到结果列表中。 返回结果 当遍历完所有层后结果列表中就存储了从上到下每一层的最右侧节点值。 java solution
class Solution {public ListInteger rightSideView(TreeNode root) {ListInteger result new ArrayList();if(root null) return result;QueueTreeNode queue new LinkedList();queue.offer(root);while(!queue.isEmpty()) {int size queue.size(); //获取当前层的节点数TreeNode rightmostNode null; //保存当前层的最右侧节点for(int i 0; i size; i) {TreeNode currentNode queue.poll(); //取出当前节点rightmostNode currentNode;if(currentNode.left ! null) queue.offer(currentNode.left);if(currentNode.right ! null) queue.offer(currentNode.right);}if(rightmostNode ! null) result.add(rightmostNode.val);}return result;}
}关键步骤解释 初始化结果列表ListInteger result new ArrayList(); 用于存储每层的最右侧节点值。 判断根节点是否为空if (root null) return result; 如果根节点为空则直接返回空列表因为没有节点可以被观察到。 使用队列来实现BFS QueueTreeNode queue new LinkedList(); 初始化一个队列。queue.offer(root); 将根节点加入队列准备开始逐层遍历。 逐层遍历 while (!queue.isEmpty()) 表示只要队列中还有节点继续进行遍历。int size queue.size(); 获取当前层的节点数量。TreeNode rightmostNode null; 初始化一个变量来保存当前层的最右侧节点。 遍历当前层的所有节点 for (int i 0; i size; i) 遍历当前层的所有节点。TreeNode currentNode queue.poll(); 从队列中取出当前节点。rightmostNode currentNode; 每次循环都会更新最右侧节点的值最后一次更新的节点就是该层的最右侧节点。if (currentNode.left ! null) queue.offer(currentNode.left); 将左子节点加入队列如果存在。if (currentNode.right ! null) queue.offer(currentNode.right); 将右子节点加入队列如果存在。 记录每层的最右侧节点 if (rightmostNode ! null) result.add(rightmostNode.val); 将当前层的最右侧节点值添加到结果列表中。 返回结果 return result; 当遍历完所有层后返回结果列表。
时间复杂度
此算法的时间复杂度为 (O(n))其中 (n) 是树中节点的数量。因为每个节点只会被访问一次。
总结
这段代码通过层序遍历来获取每层的最右侧节点从而实现了从右侧观察二叉树的效果。最终结果列表中按顺序保存了从上到下每一层的最右侧节点值符合题目要求。
