RNN梯度消失及其解决办法
月份：2019年5月
概述：完全图解RNN、RNN变体、Seq2Seq、Attention机制
二叉树路径问题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树，以及目标和 sum = 22， 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
package gongel; public class onehundred_twelve { /** * DFS */ public boolean hasPathSum(TreeNode root, int sum) { if (root == null) return false; if (root.left == null && root.right == null) return sum - root.val == 0; return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树，以及目标和 sum = 22， 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 返回: [ [5,4,11,2], [5,8,4,5] ] |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
package gongel; import java.util.ArrayList; import java.util.List; public class Onehundred_thirteen { /** * DFS+回溯 */ private List<List<Integer>> ans = new ArrayList<>(); public void finpath(TreeNode root, int sum, List<Integer> temp) { if (root != null) { if (root.left == null && root.right == null && sum == root.val) {//必须在根节点结束 temp.add(root.val); ans.add(new ArrayList<>(temp));//一定要新建一个List，否则ans中只存在一个temp temp.remove(temp.size() - 1); return; } temp.add(root.val); finpath(root.left, sum - root.val, temp); finpath(root.right, sum - root.val, temp); temp.remove(temp.size() - 1);//回溯 } } public List<List<Integer>> pathSum(TreeNode root, int sum) { List<Integer> temp = new ArrayList<>(); finpath(root, sum, temp); return ans; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
给定一个非空二叉树，返回其最大路径和。 本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。 示例 1: 输入: [1,2,3] 1 / \ 2 3 输出: 6 示例 2: 输入: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7 输出: 42 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
package gongel; public class Onehundred_twentyFour { /** * 略难！ * 最大路径和：根据当前节点的角色，路径和可分为两步： * 一：当前节点作为父节点的一个子节点 * 1.只有当前节点 * 2.当前节点+左子树 * 3.当前节点+右子树 * 这三种情况的最大值 * * 二：以当前节点为根节点 * 1.只有当前节点 * 2.当前节点+左子树 * 3.当前节点+右子树 * 4.当前节点+左右子树 * 这四种情况的最大值即为以当前节点为根的最大路径和 * 此最大值要和已经保存的最大值比较，得到整个树的最大路径值 */ private int maxValue = Integer.MIN_VALUE; public int getMaxValue(TreeNode root) { if (root == null) return 0; int leftMax = getMaxValue(root.left); int rightMax = getMaxValue(root.right); int max1 = leftMax + root.val; int max2 = rightMax + root.val; int max3 = leftMax + rightMax + root.val; //下面没有与root.val比较是因为maxValue已经初始化root.val，但也可以加上比较 maxValue = Math.max(maxValue, Math.max(max1, Math.max(max2, Math.max(max3, root.val)))); //返回的值不包括“当前节点+左右子树”，否则与父节点断开 return Math.max(root.val, Math.max(max1, max2)); } public int maxPathSum(TreeNode root) { if (root == null) return 0; //maxValue = root.val;maxValue已经为最小值了， getMaxValue(root); return maxValue; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。 例如，从根到叶子节点路径 1->2->3 代表数字 123。 计算从根到叶子节点生成的所有数字之和。 说明: 叶子节点是指没有子节点的节点。 示例 1: 输入: [1,2,3] 1 / \ 2 3 输出: 25 解释: 从根到叶子节点路径 1->2 代表数字 12. 从根到叶子节点路径 1->3 代表数字 13. 因此，数字总和 = 12 + 13 = 25. 示例 2: 输入: [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 输出: 1026 解释: 从根到叶子节点路径 4->9->5 代表数字 495. 从根到叶子节点路径 4->9->1 代表数字 491. 从根到叶子节点路径 4->0 代表数字 40. 因此，数字总和 = 495 + 491 + 40 = 1026. |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
法一：不需要回溯所以可以直接算 public class Onehundred_twentyNine { /** * dfs */ private int ans = 0; public void helper(TreeNode root, int father) { if (root != null) { int current = 10 * father + root.val; if (root.left == null && root.right == null) {//到达叶子节点 ans += current; return; } helper(root.left, current); helper(root.right, current); } } public int sumNumbers(TreeNode root) { helper(root, 0); return ans; } } 法二：利用回溯的方法，但没有回溯 public class Onehundred_twentyNine { private int ans = 0; public void dfs(TreeNode root, String path) { if (root == null) return; if (root.left == null && root.right == null) { String newPth = path + String.valueOf(root.val); ans += Integer.parseInt(newPth); return; } String newPth = path + String.valueOf(root.val); dfs(root.left, newPth); dfs(root.right, newPth); } public int sumNumbers(TreeNode root) { if (root == null) return 0; dfs(root, ""); return ans; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
给定一个二叉树，返回所有从根节点到叶子节点的路径。 说明: 叶子节点是指没有子节点的节点。 示例: 输入: 1 / \ 2 3 \ 5 输出: ["1->2->5", "1->3"] 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
package gongel; import java.util.ArrayList; import java.util.List; public class Twohundred_firtySeven { /** * dfs:不用回溯，因为link并没有改变，一般用list必须对回溯，回溯可以返回上一级 */ private List<String> ans = new ArrayList<>(); public void dfs(TreeNode root, String link) { if (root != null) { if (root.left == null && root.right == null) {//到达叶子节点 ans.add(link + root.val);//叶子节点不用+"->"，比首节点更好判断 return; } dfs(root.left, link + root.val + "->");//不需要回溯，因为link没有改变 dfs(root.right, link + root.val + "->"); } } public List<String> binaryTreePaths(TreeNode root) { if (root != null) dfs(root, new String()); return ans; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
给定一个二叉树，它的每个结点都存放着一个整数值。 找出路径和等于给定数值的路径总数。 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。 示例： root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1 返回 3。和等于 8 的路径有: 1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
package gongel; public class Fourhundred_thirtySeven { /** * 不从根节点出发即树的遍历，不从叶节点结束即不需要判断是否到了叶节点 * 先序遍历（任何遍历都可以）每一个节点，然后每个节点进行dfs */ private int ans = 0; public void dfs(TreeNode root, int sum) { if (root != null) { if (sum == root.val) { ans++; // return; 不需要return，因为即使出现负值，还会有子节点加上去 } dfs(root.left, sum - root.val); dfs(root.right, sum - root.val); } } public int pathSum(TreeNode root, int sum) { if (root != null) { dfs(root, sum); pathSum(root.left, sum); pathSum(root.right, sum); } return ans; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 示例 : 给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。 注意：两结点之间的路径长度是以它们之间边的数目表示。 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
package gongel; public class Fivehundred_fortyThree { /** * 和 124题二叉树中的最大路径和 有异曲同工之妙 */ public int ans = 0; public int dfs(TreeNode root) { if (root == null) return 0; int left = dfs(root.left);//返回左子树的最大深度 int right = dfs(root.right);//返回右子树的最大深度 ans = Math.max(ans, left + right);//最终结果的最大值 return Math.max(left, right) + 1;//求当前节点的深度（左右子树的高度最大值） } public int diameterOfBinaryTree(TreeNode root) { dfs(root); return ans; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
给定一颗根结点为 root 的二叉树，书中的每个结点都有一个从 0 到 25 的值，分别代表字母 'a' 到 'z'：值 0 代表 'a'，值 1 代表 'b'，依此类推。 找出按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。 （小贴士：字符串中任何较短的前缀在字典序上都是较小的：例如，在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。） 示例 1： 输入：[0,1,2,3,4,3,4] 输出："dba" 示例 2： 输入：[25,1,3,1,3,0,2] 输出："adz" 示例 3： 输入：[2,2,1,null,1,0,null,0] 输出："abc" 提示： 给定树的结点数介于 1 和 8500 之间。 树中的每个结点都有一个介于 0 和 25 之间的值。 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
法一：回溯 public class Ninehundred_eightyEight { /** * dfs+回溯 * 从根节点到叶子节点：逆序插入 * 每次到达叶子结点就与全局ans进行比较更新 */ private String ans = null; public void dfs(TreeNode root, StringBuffer sb) { if (root != null) { if (root.left == null && root.right == null) { sb.insert(0, (char) (root.val + 'a')); if (ans == null || sb.toString().compareTo(ans) < 0) { ans = sb.toString(); } sb.deleteCharAt(0); return; } sb.insert(0, (char) (root.val + 'a')); dfs(root.left, sb); dfs(root.right, sb); sb.deleteCharAt(0); } } public String smallestFromLeaf(TreeNode root) { dfs(root, new StringBuffer()); return ans; } } 法二：不回溯，因为path没有改变 public class Ninehundred_eightyEight { private String ans = null; public void dfs(TreeNode root, StringBuffer path) { if (root == null) return; if (root.left == null && root.right == null) { StringBuffer newPath = new StringBuffer(path); newPath.insert(0, (char) 'a' + root.val); if (ans == null) ans = newPath.toString(); if (ans.compareTo(newPath.toString()) > 0) ans = newPath.toString(); return; } StringBuffer newPath = new StringBuffer(path); newPath.insert(0, (char) 'a' + root.val); dfs(root.left, newPath); dfs(root.right, newPath); } public String smallestFromLeaf(TreeNode root) { if (root == null) return new String(); dfs(root, new StringBuffer()); return ans; } } |
