我们下面采用第二种状态：
class Solution { int n; List<String> res = new ArrayList<>(); StringBuilder sb = new StringBuilder(); public List<String> generateParenthesis(int n) { this.n = n; f(0, 0, 0); return res; } // depth为递归深度，count为左右括号配比，左括号+1，右括号-1 public void f(int depth, int left, int right) { if (left > n || right > n || left < right) { return; } if (depth >= 2 * n && left == n && right == n) { res.add(new String(sb)); return; } sb.append("("); f(depth + 1, left + 1, right); sb.delete(sb.length() - 1, sb.length()); sb.append(")"); f(depth + 1, left, right + 1); sb.delete(sb.length() - 1, sb.length()); } } 面试题 04.10. 检查子树检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。
如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。
注意：此题相对书上原题略有改动。
示例1:
输入：t1 = [1, 2, 3], t2 = [2] 输出：true示例2:
输入：t1 = [1, null, 2, 4], t2 = [3, 2] 输出：false 答案 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean checkSubTree(TreeNode t1, TreeNode t2) { if(t2 == null){ // 子树为空 return true; } if(t1 == null && t2 != null){ // 子树不为空 return false; } return isSame(t1, t2) || checkSubTree(t1.left, t2) || checkSubTree(t1.right, t2); } public boolean isSame(TreeNode t1, TreeNode t2) { // if (t1 == t2) { // return true; // } // 同时为空 if (t1 == null && t2 == null) { return true; } // 不同时为空 if (t1 == null || t2 == null){ return false; } return t1.val == t2.val && isSame(t1.left, t2.left) && isSame(t1.right, t2.right); } } 面试题 04.01. 节点间通路节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
示例1:
输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2 输出：true示例2:
输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4 输出 true 答案一：从前往后因为测试用例start的路径太多了，所以导致从start开始会超时
class Solution { boolean flag; boolean[] used; public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) { used = new boolean[graph.length]; f(n, graph, start, target); return flag; } public void f(int n, int[][] graph, int start, int target) { if (start == target || flag == true) { flag = true; return; } // 因为测试用例start的路径太多了，所以导致从start开始会超时 for (int i = 0; i < graph.length; i++) { if (used[i] == false && graph[i][0] == start && graph[i][1] == target) { flag = true; return; } if (graph[i][0] == start && graph[i][1] == target) { flag = true; return; } } } } 答案二：从后往前测试用例中target的路径比较少，所以不会超时。
class Solution { boolean flag; boolean[] used; public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) { used = new boolean[graph.length]; f(n, graph, start, target); return flag; } public void f(int n, int[][] graph, int start, int target) { if (start == target || flag == true) { flag = true; return; } // 因为测试用例start的路径太多了，所以导致从start开始会超时 // for (int i = 0; i < graph.length; i++) { // if (graph[i][0] == start && graph[i][1] == target) { // flag = true; // return; // } // } // 所以我换了一种思路，从后往前，从target开始，就不会超时了 for (int i = 0; i < graph.length; i++) { if (used[i] == false && graph[i][0] == start && graph[i][1] == target) { flag = true; return; } if (used[i] == false && graph[i][1] == target) { used[i] = true; f(n, graph, start, graph[i][0]); used[i] = false; } } } } 答案二：从后往前另一种实现 class Solution { private boolean[] visited = null; public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) { this.visited = new boolean[graph.length]; return helper(graph, start, target); } private boolean helper(int[][] graph, int start, int target) { for (int i = 0; i < graph.length; ++i) { if (!visited[i]) { if (graph[i][0] == start && graph[i][1] == target) { return true; } visited[i] = true; if (graph[i][1] == target && helper(graph, start, graph[i][0])) { return true; } visited[i] = false; } } return false; } }