- 正确答案：获取二叉树每层最右节点的方法是使用层序遍历（广度优先搜索，BFS），在每一层的遍历过程中记录最后一个被访问的节点，即为该层的最右节点。也可以使用深度优先搜索（DFS）按右子树优先的顺序递归，首次到达某一层时的节点即为该层最右节点。 - 解答思路： 1. 方法一：使用队列进行层序遍历（BFS）。每一轮处理一层节点，将该层所有节点出队，并将下一层节点入队。每层最后一个出队的节点就是该层的最右节点。 2. 方法二：使用深度优先搜索（DFS），优先访问右子树。使用一个数组或列表记录每一层第一个被访问到的节点（因为右子树先访问，所以第一次到达某层时的节点就是最右节点）。两种方法都能正确获取每层最右节点，BFS更直观，DFS在某些情况下空间效率更高（尤其是完全二叉树）。 - 深度知识讲解： 1. 层序遍历（BFS）基于队列实现，是典型的广度优先策略。队列的先进先出（FIFO）特性保证了节点按层级顺序被处理。每一层的节点数可以通过当前队列大小确定，从而实现分层处理。 2. DFS 方法利用递归栈，按先右后左的顺序遍历，确保每层最右边的节点最先被访问。通过维护一个 level 表示当前深度，以及一个结果列表 result，当 result.size() == level 时，说明这是第一次访问该层，将当前节点加入结果列表。 3. 时间复杂度均为 O(n)，n 为二叉树节点数，因为每个节点访问一次。空间复杂度方面，BFS 为 O(w)，w 为树的最大宽度；DFS 为 O(h)，h 为树的高度（递归栈深度）。 4. 底层数据结构： - 队列（BFS）：通常用双端队列或动态数组实现，支持在尾部添加、头部删除。 - 递归栈（DFS）：由函数调用栈维护，每个调用帧保存局部变量和参数。应用场景：该问题常见于树的视图问题，如“右视图”（right view of binary tree），即从右侧看树能看到的节点，正好是每层最右节点。 - 代码示例（BFS 方法）： ``` import java.util.*; class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public List rightSideView(TreeNode root) { List result = new ArrayList<>(); if (root == null) return result; Queue queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); // 当前层的节点数 for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); // 每层最后一个节点即为最右节点 if (i == levelSize - 1) { result.add(node.val); } // 将子节点加入队列 if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } } return result; } ``` - 代码示例（DFS 方法）： ``` public List rightSideView(TreeNode root) { List result = new ArrayList<>(); dfs(root, 0, result); return result; } private void dfs(TreeNode node, int level, List result) { if (node == null) return; // 如果是该层第一个访问的节点（右子树优先），则加入结果 if (result.size() == level) { result.add(node.val); } // 先递归右子树，再左子树 dfs(node.right, level + 1, result); dfs(node.left, level + 1, result); } ``` - 扩展知识点： 1. 类似问题：每层最左节点（左视图）、层平均值、树的左视图等，均可通过 BFS 或 DFS 变种解决。 2. 完全二叉树中，最右节点可能位于最深层，可用于判断树的结构完整性。 3. 在数据库或文件系统的层次结构展示中，类似算法可用于生成层级摘要或可视化视图。 4. 进阶：若要求每层最右节点的路径，可在遍历时记录父节点或路径信息，使用回溯法。总结：该问题考察对树的遍历方式（BFS vs DFS）的理解，以及对层级结构的处理能力。掌握其底层实现有助于应对各类树形结构的遍历与视图问题。

百度健康一面

全站热榜

创作者周榜