publicstaticvoiddfs2(int[][] matrix, int x, int y, boolean[][] visited, List<Integer> res){ if (x >= 0 && y >= 0 && x < matrix.length && y < matrix[0].length && !visited[x][y]) { visited[x][y] = true; res.add(matrix[x][y]); dfs2(matrix, x - 1, y, visited, res); dfs2(matrix, x, y + 1, visited, res); } }
接下来就是构建BST的过程代码辣:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
publicstaticvoidbuildBst(int n, TreeNode root){ if (n <= root.val) { if (root.left == null) { root.left = new TreeNode(n); } else { root = root.left; buildBst(n, root); } } else { if (root.right == null) { root.right = new TreeNode(n); } else { root = root.right; buildBst(n, root); } }
publicclassKthSmallestElementInaSortedMatrix{ publicstaticintkthSmallest(int[][] matrix, int k){ List<Integer> tmp = new ArrayList<>(); List<Integer> res = new ArrayList<>();
boolean[][] visited = newboolean[matrix.length][matrix[0].length]; dfs2(matrix, matrix.length - 1, 0, visited, tmp); TreeNode root = new TreeNode(tmp.get(0)); // 第一位是root节点,已经add了 for (int i = 1; i < tmp.size(); i++) { buildBst(tmp.get(i), root); } dfs(root, res); return res.get(k - 1); }
publicstaticvoidbuildBst(int n, TreeNode root){ if (n <= root.val) { if (root.left == null) { root.left = new TreeNode(n); } else { root = root.left; buildBst(n, root); } } else { if (root.right == null) { root.right = new TreeNode(n); } else { root = root.right; buildBst(n, root); } }
publicstaticvoiddfs2(int[][] matrix, int x, int y, boolean[][] visited, List<Integer> res){ if (x >= 0 && y >= 0 && x < matrix.length && y < matrix[0].length && !visited[x][y]) { visited[x][y] = true; res.add(matrix[x][y]); dfs2(matrix, x - 1, y, visited, res); dfs2(matrix, x, y + 1, visited, res); } }
} classTreeNode{
publicint val; public TreeNode left; public TreeNode right;
publicTreeNode(int x){ val = x; }
@Override public String toString(){ return"TreeNode{" + "val=" + val + ", left=" + left + ", right=" + right + '}'; } }