算法练习4

今日完成 4 道二叉树高频题覆盖两类核心模型BFS使用队列按层处理节点。 递归先获得左右子树结果再合并为当前节点结果。1. 二叉树的最大深度题目给定二叉树根节点求从根节点到最远叶子节点路径上的节点数量。示例3 / \ 9 20 / \ 15 7 最大深度3递归思路对于任意节点当前节点最大深度 max(左子树最大深度, 右子树最大深度) 1其中空节点深度为 0。 1 表示当前节点这一层。Java 实现public int maxDepth(TreeNode root) { if (root null) { return 0; } int leftDepth maxDepth(root.left); int rightDepth maxDepth(root.right); return Math.max(leftDepth, rightDepth) 1; }复杂度时间复杂度O(n) 空间复杂度O(h)n是节点数量h是树高。递归调用栈的最大深度等于树高。递归模板1. 空节点时返回基础值。 2. 递归处理左子树。 3. 递归处理右子树。 4. 合并左右子树结果。2. 二叉树的层序遍历题目按照从上到下、每层从左到右的顺序遍历二叉树。示例3 / \ 9 20 / \ 15 7 结果[[3], [9, 20], [15, 7]]核心队列 BFS层序遍历使用队列因为队列是先进先出根节点先入队 先处理根节点 根节点的左右孩子后入队 再处理下一层节点。队列保存的是TreeNode节点引用QueueTreeNode queue new ArrayDeque();每一层处理前先记录当前队列长度int levelSize queue.size();这个levelSize表示当前层一共有多少节点。循环中加入的子节点属于下一层不能与当前层混在一起处理。Java 实现public ListListInteger levelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) { return result; } QueueTreeNode queue new ArrayDeque(); queue.add(root); while (!queue.isEmpty()) { int levelSize queue.size(); ListInteger currentLevel new ArrayList(); for (int i 0; i levelSize; i) { TreeNode node queue.remove(); currentLevel.add(node.val); if (node.left ! null) { queue.add(node.left); } if (node.right ! null) { queue.add(node.right); } } result.add(currentLevel); } return result; }队列常用操作queue.add(node); // 从队尾加入节点 queue.remove(); // 从队头取出并删除节点 queue.peek(); // 查看队头节点不删除 queue.isEmpty(); // 判断队列是否为空 queue.size(); // 当前队列中节点数量复杂度时间复杂度O(n) 空间复杂度O(n)3. 二叉树的右视图题目从二叉树右侧观察返回每一层最右边可见的节点值。示例1 / \ 2 3 \ \ 5 4 结果[1, 3, 4]思路复用层序遍历右视图不是只遍历右子树。例如1 / 2 / 3右视图仍然是[1, 2, 3]因为每层只有一个节点它自然就是右侧可见节点。正确做法是遍历每一层的所有节点 从左到右处理 记录当前层最后一个节点。在当前层循环中if (i levelSize - 1) { result.add(node.val); }因为i levelSize - 1表示当前节点是这一层从左到右处理的最后一个节点。Java 实现public ListInteger rightSideView(TreeNode root) { ListInteger result new ArrayList(); if (root null) { return result; } QueueTreeNode queue new ArrayDeque(); queue.add(root); while (!queue.isEmpty()) { int levelSize queue.size(); for (int i 0; i levelSize; i) { TreeNode node queue.remove(); if (i levelSize - 1) { result.add(node.val); } if (node.left ! null) { queue.add(node.left); } if (node.right ! null) { queue.add(node.right); } } } return result; }复杂度时间复杂度O(n) 空间复杂度O(n)4. 二叉树的直径题目求二叉树中任意两个节点之间的最长路径边数。注意最长路径不一定经过根节点。示例1 / \ 2 3 / \ 4 5 最长路径4 - 2 - 1 - 3 直径3 条边核心思路对于每一个节点经过当前节点的最长路径边数 左子树高度 右子树高度但最终答案需要取所有节点中的最大值全局直径 max(每个节点的左子树高度 右子树高度)递归函数有两个职责1. 返回当前节点的高度供父节点使用。 2. 用左右子树高度之和更新全局直径。高度与直径的区别当前节点高度max(左子树高度, 右子树高度) 1经过当前节点的路径边数左子树高度 右子树高度例如2 / \ 4 5左高度 1 右高度 1 经过节点 2 的最长路径4 - 2 - 5 路径边数1 1 2 节点 2 的高度max(1, 1) 1 2Java 实现private int maxDiameter; public int diameterOfBinaryTree(TreeNode root) { maxDiameter 0; getHeight(root); return maxDiameter; } private int getHeight(TreeNode node) { if (node null) { return 0; } int leftHeight getHeight(node.left); int rightHeight getHeight(node.right); maxDiameter Math.max(maxDiameter, leftHeight rightHeight); return Math.max(leftHeight, rightHeight) 1; }复杂度时间复杂度O(n) 空间复杂度O(h)每个节点只访问一次递归栈深度由树高决定。