@[toc]
一、矩阵中的路径
public boolean exist(char[][] board, String word) {
char[] words = word.toCharArray();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (dfs(board, words, i, j, 0)) {
return true;
}
}
}
return false;
}
boolean dfs(char[][] board, char[] word, int i, int j, int k) {
if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) {
return false;
}
if (k == word.length - 1) {
return true;
}
board[i][j] = '\0';
boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i, j - 1, k + 1);
board[i][j] = word[k];
return res;
}二、机器人的运动范围
int m, n, k;
boolean[][] visited;
public int movingCount(int m, int n, int k) {
this.m = m; this.n = n; this.k = k;
this.visited = new boolean[m][n];
return dfs(0, 0, 0, 0);
}
public int dfs(int i, int j, int si, int sj) {
if(i >= m || j >= n || k < si + sj || visited[i][j]) return 0;
visited[i][j] = true;
return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);
}三、树的子结构
public boolean isSubStructure(TreeNode A, TreeNode B) {
return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
}
boolean recur(TreeNode A, TreeNode B) {
if(B == null) {
return true;
}
if(A == null || A.val != B.val) {
return false;
}
return recur(A.left, B.left) && recur(A.right, B.right);
}四、二叉树的镜像
public TreeNode mirrorTree(TreeNode root) {
if(root == null) {
return null;
}
TreeNode tmp = root.left;
root.left = mirrorTree(root.right);
root.right = mirrorTree(tmp);
return root;
}五、对称的二叉树
public boolean isSymmetric(TreeNode root) {
return root == null || recur(root.left, root.right);
}
boolean recur(TreeNode L, TreeNode R) {
if(L == null && R == null) {
return true;
}
if(L == null || R == null || L.val != R.val) {
return false;
}
return recur(L.left, R.right) && recur(L.right, R.left);
}六、从上到下打印二叉树 I
public int[] levelOrder(TreeNode root) {
if (root == null) {
return new int[0];
}
List<TreeNode> list = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
list.add(node);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
int[] arr = new int[list.size()];
for (int i = 0; i < arr.length; i++) {
arr[i] = list.get(i).val;
}
return arr;
}七、从上到下打印二叉树 II
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
if(root != null) {
queue.add(root);
}
while(!queue.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
for(int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
tmp.add(node.val);
if(node.left != null) {
queue.add(node.left);
}
if(node.right != null) {
queue.add(node.right);
}
}
res.add(tmp);
}
return res;
}八、从上到下打印二叉树 III
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
if(root != null) {
queue.add(root);
}
while(!queue.isEmpty()) {
LinkedList<Integer> tmp = new LinkedList<>();
for(int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
if(res.size() % 2 == 0) {
tmp.addLast(node.val);
} else {
tmp.addFirst(node.val);
}
if(node.left != null) {
queue.add(node.left);
}
if(node.right != null) {
queue.add(node.right);
}
}
res.add(tmp);
}
return res;
}九、二叉树中和为某一值的路径
List<List<Integer>> res;
public List<List<Integer>> pathSum(TreeNode root, int target) {
if (root == null) {
return new ArrayList<>();
}
res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
list.add(root.val);
dfs(root, list, root.val, target);
return res;
}
public void dfs(TreeNode node, List<Integer> list, int sum, int target) {
if (sum == target && node.left == null && node.right == null) {
res.add(new ArrayList<>(list));
}
if (node.left != null) {
list.add(node.left.val);
dfs(node.left, list, sum + node.left.val, target);
list.remove(list.size() - 1);
}
if (node.right != null) {
list.add(node.right.val);
dfs(node.right, list, sum + node.right.val, target);
list.remove(list.size() - 1);
}
}十、二叉搜索树与双向链表
Node pre, head;
public Node treeToDoublyList(Node root) {
if(root == null) {
return null;
}
dfs(root);
head.left = pre;
pre.right = head;
return head;
}
void dfs(Node cur) {
if(cur == null) {
return;
}
dfs(cur.left);
if(pre != null) {
pre.right = cur;
} else {
head = cur;
}
cur.left = pre;
pre = cur;
dfs(cur.right);
}十一、序列化二叉树
public String serialize(TreeNode root) {
if (root == null) {
return "[]";
}
StringBuilder res = new StringBuilder("[");
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
res.append(node.val + ",");
queue.add(node.left);
queue.add(node.right);
} else {
res.append("null,");
}
}
res.deleteCharAt(res.length() - 1);
res.append("]");
return res.toString();
}
public TreeNode deserialize(String data) {
if (data.equals("[]")) {
return null;
}
String[] vals = data.substring(1, data.length() - 1).split(",");
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int i = 1;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (!vals[i].equals("null")) {
node.left = new TreeNode(Integer.parseInt(vals[i]));
queue.add(node.left);
}
i++;
if (!vals[i].equals("null")) {
node.right = new TreeNode(Integer.parseInt(vals[i]));
queue.add(node.right);
}
i++;
}
return root;
}十二、字符串的排列
List<String> res = new LinkedList<>();
char[] c;
public String[] permutation(String s) {
c = s.toCharArray();
dfs(0);
return res.toArray(new String[res.size()]);
}
void dfs(int x) {
if(x == c.length - 1) {
res.add(String.valueOf(c)); // 添加排列方案
return;
}
HashSet<Character> set = new HashSet<>();
for(int i = x; i < c.length; i++) {
if(set.contains(c[i])) {
continue; // 重复，因此剪枝
}
set.add(c[i]);
swap(i, x); // 交换，将 c[i] 固定在第 x 位
dfs(x + 1); // 开启固定第 x + 1 位字符
swap(i, x); // 恢复交换
}
}
void swap(int a, int b) {
char tmp = c[a];
c[a] = c[b];
c[b] = tmp;
}十三、二叉搜索树的第 k 大节点
int res, k;
public int kthLargest(TreeNode root, int k) {
this.k = k;
dfs(root);
return res;
}
void dfs(TreeNode root) {
if(root == null) {
return;
}
dfs(root.right);
if(k == 0) {
return;
}
if(--k == 0) {
res = root.val;
}
dfs(root.left);
}十四、二叉树的深度
public int maxDepth(TreeNode root) {
return maxDepth(root, 1);
}
public int maxDepth(TreeNode node, int curHeight) {
if (node == null) {
return curHeight - 1;
}
return Math.max(maxDepth(node.left, curHeight + 1), maxDepth(node.right, curHeight + 1));
}--
十五、平衡二叉树
boolean isBalanced = true;
public boolean isBalanced(TreeNode root) {
maxDepth(root);
return isBalanced;
}
public int maxDepth(TreeNode root) {
return maxDepth(root, 1);
}
public int maxDepth(TreeNode node, int curHeight) {
if (node == null || !isBalanced) {
return curHeight - 1;
}
int lh = maxDepth(node.left, curHeight + 1);
int rh = maxDepth(node.right, curHeight + 1);
if (Math.abs(lh - rh) > 1) {
isBalanced = false;
}
return Math.max(lh, rh);
}十六、求 1 + 2 + … + n
public int sumNums(int n) {
return dfs(n, 0);
}
public int dfs(int n, int res) {
if (n > 0) {
return dfs(n - 1, res + n);
}
return res;
}十七、二叉搜索树的最近公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(p.val > q.val) { // 保证 p.val < q.val
TreeNode tmp = p;
p = q;
q = tmp;
}
while(root != null) {
if(root.val < p.val) // p,q 都在 root 的右子树中
{
root = root.right; // 遍历至右子节点
} else if(root.val > q.val) // p,q 都在 root 的左子树中
{
root = root.left; // 遍历至左子节点
} else {
break;
}
}
return root;
}十八、二叉树的最近公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left == null && right == null) {
return null; // 1.
}
if(left == null) {
return right; // 3.
}
if(right == null) {
return left; // 4.
}
return root; // 2. if(left != null and right != null)
}
