LeetCode题解——树(二) 不念不忘少年蓝@ 2023-02-16 00:43 38阅读 0赞 ### 文章目录 ### * 递归 * * 二叉树的最小深度 * * 递归解法 * 对称二叉树 * * 递归解法 * 迭代解法 * 左叶子之和 * * 递归解法 * 最长同值路径 * * 递归解法 * 打家劫舍 III * * 递归解法 * 动态规划 * 二叉树中第二小的节点 * * 递归解法 * 层序遍历 * * 二叉树的层平均值 * * 层序遍历 * DFS * 找树左下角的值 * * 层序遍历 * DFS * * 推荐阅读 # 递归 # ## 二叉树的最小深度 ## 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回它的最小深度 2. ### 递归解法 ### /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int minDepth(TreeNode root) { if (root == null) { return 0; } int left = minDepth(root.left); int right = minDepth(root.right); if (left == 0 || right == 0) { return left + right + 1; } return Math.min(left, right) + 1; } } ## 对称二叉树 ## 给定一个二叉树,检查它是否是镜像对称的。 例如,二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ / \ 3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1 / \ 2 2 \ \ 3 3 进阶: 你可以运用递归和迭代两种方法解决这个问题吗? ### 递归解法 ### /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSymmetric(TreeNode root) { if (root == null) { return true; } return isSymmetric(root.left, root.right); } public boolean isSymmetric(TreeNode t1, TreeNode t2) { if (t1 == null && t2 == null) { return true; } if (t1 == null || t2 == null) { return false; } if (t1.val != t2.val) { return false; } return isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left); } } ### 迭代解法 ### /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSymmetric(TreeNode root) { if (root == null) { return true; } return isSymmetric(root.left, root.right); } public boolean isSymmetric(TreeNode t1, TreeNode t2) { Queue<TreeNode> queue = new LinkedList<>(); queue.offer(t1); queue.offer(t2); while (!queue.isEmpty()) { t1 = queue.poll(); t2 = queue.poll(); if (t1 == null && t2 == null) { continue; } if (t1 == null || t2 == null || t1.val != t2.val) { return false; } queue.offer(t1.left); queue.offer(t2.right); queue.offer(t1.right); queue.offer(t2.left); } return true; } } ## 左叶子之和 ## 计算给定二叉树的所有左叶子之和。 示例: 3 / \ 9 20 / \ 15 7 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24 ### 递归解法 ### /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int sumOfLeftLeaves(TreeNode root) { if (root == null) { return 0; } if (isLeaf(root.left)) { return root.left.val + sumOfLeftLeaves(root.right); } return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right); } private boolean isLeaf(TreeNode node) { if (node == null) { return false; } return node.left == null && node.right == null; } } ## 最长同值路径 ## 给定一个二叉树,找到最长的路径,这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。 注意:两个节点之间的路径长度由它们之间的边数表示。 示例 1: 输入: 5 / \ 4 5 / \ \ 1 1 5 输出: 2 示例 2: 输入: 1 / \ 4 5 / \ \ 4 4 5 输出: 2 注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。 ### 递归解法 ### /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { private int path = 0; public int longestUnivaluePath(TreeNode root) { dfs(root); return path; } private int dfs(TreeNode root) { if (root == null) { return 0; } int left = dfs(root.left); int right = dfs(root.right); int leftDepth = root.left != null && root.val == root.left.val ? left + 1 : 0; int rightDepth = root.right != null && root.val == root.right.val ? right + 1 : 0; path = Math.max(path, leftDepth + rightDepth); return Math.max(leftDepth, rightDepth); } } ## 打家劫舍 III ## 在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。 计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。 示例 1: 输入: [3,2,3,null,3,null,1] 3 / \ 2 3 \ \ 3 1 输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7. 示例 2: 输入: [3,4,5,1,3,null,1] 3 / \ 4 5 / \ \ 1 3 1 输出: 9 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9. ### 递归解法 ### /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int rob(TreeNode root) { if (root == null) { return 0; } int val1 = root.val; if (root.left != null) { val1 += rob(root.left.left) + rob(root.left.right); } if (root.right != null) { val1 += rob(root.right.left) + rob(root.right.right); } int val2 = rob(root.left) + rob(root.right); return Math.max(val1, val2); } } ### 动态规划 ### 以上递归解法,子树最优值有的计算多遍,下面提供一种动态规划解法。教程详见[https://leetcode-cn.com/problems/house-robber-iii/solution/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/][https_leetcode-cn.com_problems_house-robber-iii_solution_san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu] /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int rob(TreeNode root) { int[] result = robInternal(root); return Math.max(result[0], result[1]); } private int[] robInternal(TreeNode root) { if (root == null) { return new int[2]; } int[] result = new int[2]; int[] left = robInternal(root.left); int[] right = robInternal(root.right); result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); result[1] = left[0] + right[0] + root.val; return result; } } ## 二叉树中第二小的节点 ## 给定一个非空特殊的二叉树,每个节点都是正数,并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话,那么这个节点的值不大于它的子节点的值。 给出这样的一个二叉树,你需要输出所有节点中的第二小的值。如果第二小的值不存在的话,输出 -1 。 示例 1: 输入: 2 / \ 2 5 / \ 5 7 输出: 5 说明: 最小的值是 2 ,第二小的值是 5 。 示例 2: 输入: 2 / \ 2 2 输出: -1 说明: 最小的值是 2, 但是不存在第二小的值。 ### 递归解法 ### /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int findSecondMinimumValue(TreeNode root) { if (root == null || (root.left == null && root.right == null)) { return -1; } int leftVal = root.left.val; int rightVal = root.right.val; if (leftVal == root.val) { leftVal = findSecondMinimumValue(root.left); } if (rightVal == root.val) { rightVal = findSecondMinimumValue(root.right); } if (rightVal != -1 && leftVal != -1) { return Math.min(rightVal, leftVal); } if (rightVal == -1) { return leftVal; } return rightVal; } } # 层序遍历 # ## 二叉树的层平均值 ## 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组. 示例 1: 输入: 3 / \ 9 20 / \ 15 7 输出: [3, 14.5, 11] 解释: 第0层的平均值是 3, 第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11]. 注意: 节点值的范围在32位有符号整数范围内。 ### 层序遍历 ### /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Double> averageOfLevels(TreeNode root) { List<Double> ret = new ArrayList<>(); if (root == null) { return ret; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { double sum = 0; int size = queue.size(); for (int i = 0; i < size; ++i) { TreeNode node = queue.poll(); sum += node.val; if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } ret.add(sum / size); } return ret; } } ### DFS ### /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Double> averageOfLevels(TreeNode root) { List<Double> ret = new ArrayList<>(); if (root == null) { return ret; } List<Integer> count = new ArrayList<>(); dfs(root, 0, ret, count); for (int i = 0; i < ret.size(); ++i) { ret.set(i, ret.get(i) / count.get(i)); } return ret; } private void dfs(TreeNode t, int i, List<Double> sum, List<Integer> count) { if (t == null) { return; } if (i < sum.size()) { sum.set(i, sum.get(i) + t.val); count.set(i, count.get(i) + 1); } else { sum.add(i, 1.0 * t.val); count.add(1); } dfs(t.left, i + 1, sum, count); dfs(t.right, i + 1, sum, count); } } ## 找树左下角的值 ## 给定一个二叉树,在树的最后一行找到最左边的值。 示例 1: 输入: 2 / \ 1 3 输出: 1 示例 2: 输入: 1 / \ 2 3 / / \ 4 5 6 / 7 输出: 7 注意: 您可以假设树(即给定的根节点)不为 NULL。 ### 层序遍历 ### /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int findBottomLeftValue(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); int result = 0; while(!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; ++i) { TreeNode node = queue.poll(); if (i == 0) { result = node.val; } if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } } return result; } } ### DFS ### /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int max = -1; int result = 0; public int findBottomLeftValue(TreeNode root) { dfs(root, 0); return result; } private void dfs(TreeNode node, int hight) { if (node == null) { return; } if (hight > max) { // 第一次大于max,就代表进入了新一层,当前结点就是最左结点 max = hight; result = node.val; } dfs(node.left, hight + 1); dfs(node.right, hight + 1); } } -------------------- #### 推荐阅读 #### * [机器学习资料汇总][Link 1] * [吴恩达《机器学习》视频、作业、源码][Link 2] * [106页《Python进阶》中文版正式发布][106_Python] * [李航《统计学习方法》第二版完整课件][Link 3] * [机器学习数学全书,1900页PDF下载][1900_PDF] -------------------- ![format_png][] [https_leetcode-cn.com_problems_house-robber-iii_solution_san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu]: https://leetcode-cn.com/problems/house-robber-iii/solution/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/ [Link 1]: https://mp.weixin.qq.com/s/3nOkk_Yt9D7Qp1WaWEjyZQ [Link 2]: https://mp.weixin.qq.com/s/dErZNtBYbVA7ItPm7T_HIw [106_Python]: https://mp.weixin.qq.com/s/_WEuuxj-QgihijjLz7NJ9g [Link 3]: https://mp.weixin.qq.com/s/xah47OWuu8ahAUa1aFFo4Q [1900_PDF]: https://mp.weixin.qq.com/s/9BuyhdwuHiHH3ksVUe44ZQ [format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9Gc2lzMkxhbzF6UkEtUnBic1RFREEwX3owNHdi?x-oss-process=image/format,png
相关 LeetCode题解——动态规划(二) 文章目录 303. 区域和检索 - 数组不可变 缓存 413. 等差数列划分 常数内存的动态规划 客官°小女子只卖身不卖艺/ 2023年07月06日 11:54/ 0 赞/ 68 阅读
相关 LeetCode题解--回溯算法(二) 文章目录 46. 全排列 回溯算法 47. 全排列 II 回溯算法 77. 组合 àì夳堔傛蜴生んèń/ 2023年06月20日 06:25/ 0 赞/ 39 阅读
相关 LeetCode题解——贪心算法(二) 文章目录 435. 无重叠区间 按起点排序的贪心算法 统计移除区间数 统计保留区间数 忘是亡心i/ 2023年06月06日 07:49/ 0 赞/ 24 阅读
相关 LeetCode题解——数学问题(二) 文章目录 七进制数 数字转换为十六进制数 Excel表列名称 阶乘后的零 解法 ゞ 浴缸里的玫瑰/ 2023年02月13日 14:50/ 0 赞/ 127 阅读
相关 LeetCode系列题解之 二叉搜索树系列题解 文章目录 二叉搜索树 前言 两个基础的框架部分 具体示例 简单实现版: \[ ╰半橙微兮°/ 2022年11月25日 13:08/ 0 赞/ 159 阅读
相关 leetcode题解——617.合并二叉树 给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的 矫情吗;*/ 2022年01月11日 09:51/ 0 赞/ 182 阅读
还没有评论,来说两句吧...