版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_43126117/article/details/100548551
题解:一看就是搜索问题,根据层次遍历出所有元素。用广度优先搜索算法简单。
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> lists = new ArrayList<>();
if (root == null) return lists;
Queue<TreeNode> queue = new LinkedList<>(); //使用队列保存同一层节点
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size(); //得到队列中同一层 有N个
List<Integer> list = new ArrayList<>();
for (int i = 0; i < size; i++) { //遍历N次,即取出队列中同一层节点
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) queue.add(node.left); //下一层节点先保存到队列中
if (node.right != null) queue.add(node.right);
}
lists.add(list);
}
return lists;
}
深度优先搜索也是可以的,只需要携带层次信息,在存储时选择合适位置即可。
List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<List<Integer>> levelOrder2(TreeNode root) {
if (root == null) return result;
DFS(root, 0);
return result;
}
public void DFS(TreeNode node, int level) {
if (result.size() == level) result.add(new ArrayList<>());
if (node.left != null) DFS(node.left, level + 1);
if (node.right != null) DFS(node.right, level + 1);
result.get(level).add(node.val); //选择合适的层次list
}
题解:也是搜索问题,只是搜索结束条件要看清楚,是当前节点没有左右节点时为最大深度。也就是一个深度优先搜索算法。
//一开始做的dfs,通过当前节点没有左右节点时保存 当前层次
private int max = 0;
public int maxDepth2(TreeNode root) {
if (root == null) return 0;
DFS(root, 1);
return max;
}
public void DFS(TreeNode node, int level) {
if (node.left != null) DFS(node.left, level + 1);
if (node.right != null) DFS(node.right, level + 1);
if (level > max) max = level; //当前层数与之前最大层数相比较
}
//下面这个解法比较简洁,是通过 循环计算左右节点层数 从0开始依此加1,再左右比较,保留最大+1。
//并不需要考虑左右节点
public int maxDepth(TreeNode root) {
if (root == null) return 0; /递归出口
int left_height = maxDepth(root.left);
int right_height = maxDepth(root.right);
return java.lang.Math.max(left_height, right_height) + 1;
}
跟上一题很像,走完一层就加一,直到最后一层
public int maxDepth3(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
level++; //队列中同层已经出完,加一
}
return level;
}
这个和上一题有区别在于,max改为min也不行,当9有左节点没有右节点的时候 ,还会返回1。当前节点只有一侧节点时,上一题解法就错误了。下面做法保证当前节点没有左右节点才输出。
public int minDepth(TreeNode root) {
if (root == null) return 0;
// 左孩子为空,只考虑右孩子的方向
if (root.left == null) return minDepth(root.right) + 1;
// 右孩子为空,只考虑左孩子的方向
if (root.right == null) return minDepth(root.left) + 1;
int left_height = minDepth(root.left);
int right_height = minDepth(root.right);
return java.lang.Math.min(left_height, right_height) + 1;
}
最先一层的某个节点没有左右节点时,即返回。这样算法效率应该更高。
public int minDepth2(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int level = 0;
while (!queue.isEmpty()) {
level++;
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
if (node.left == null && node.right == null) return level; //第一个没有左右节点,即返回
}
}
return level;
}
题解:也是搜索的问题,假如用穷举得到所有结果,再从中找正确的结果。也是可行的,但是写的会特别复杂。这里可以利用剪枝的概念,先去掉不必要的解,比如左括号在第一位,左右括号数应该相等,左括号先写入再写右括号等。
public List<String> generateParenthesis(int n) {
List<String> list = new ArrayList<>();
prun("", list, n, n);
return list;
}
public void prun(String str, List<String> list, int leftsize, int rightsize) {//第一步剪枝:左右括号个数相同
if (leftsize > 0) prun(str + "(", list, leftsize - 1, rightsize);//第二步剪枝:保证左括号先写入
if (leftsize < rightsize) prun(str + ")", list, leftsize, rightsize - 1);//第三步剪枝:保证写入左右括号相同
if (rightsize == 0) list.add(str);
}
//这个递归是有一个回溯的过程的,这里隐藏了,下面这种做法可看出来。
class Solution {
public List<String> generateParenthesis(int n) {
List<String> list = new ArrayList<>();
StringBuffer str = new StringBuffer();
prun(str, list, n, n);
return list;
}
public void prun(StringBuffer str, List<String> list, int leftsize, int rightsize) {
if (leftsize > 0) {
str.append("(");
prun(str, list, leftsize - 1, rightsize);
str.deleteCharAt(str.length() - 1); //递归返回字符串需要保持原有的,即回溯
}
if (leftsize < rightsize) {
str.append(")");
prun(str, list, leftsize, rightsize - 1);
str.deleteCharAt(str.length() - 1);
}
if (rightsize == 0) list.add(str.toString());
}
}
题解:皇后不能相互攻击,即如图画红线的位置不能有另外一个皇后,这个解法也就是把四条红线用代码表示出来。
下面这个解法是比较容易理解的
class Solution51 {
int n;
int row[]; //行列
int hills[]; //撇
int dales[]; //捺
int queens[]; //皇后位置
List<List<String>> lists = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
this.n = n;
row = new int[n];
hills = new int[2 * n]; //2n作用:保证有存储的数组。
dales = new int[4 * n];
queens = new int[n];
DFS(0);
return lists;
}
public void DFS(int num) {
for (int i = 0; i < n; i++) {//填第num行i个皇后所处的位置queens[0]=0,表明第1行的皇后位于第1列
if (row[i] + hills[num + i] + dales[num - i + 2 * n] == 0) {//检测当前填入的皇后与之前的所有皇后是否冲突
placeQueen(num, i, true); //更改四条红线状态
if (num + 1 == n) addQueen(); //找到其中一个解法
else DFS(num + 1); //递归,下一行
placeQueen(num, i, false); //回溯,还原四条红线状态
}
}
}
private void addQueen() {
List<String> list = new ArrayList<>();
for (int i : queens) {
StringBuffer str = new StringBuffer();
for (int j = 0; j < i; j++) str.append(".");
str.append("Q");
for (int j = i+1; j < n ; j++) str.append(".");
list.add(str.toString());
}
lists.add(list);
}
private void placeQueen(int num, int i, boolean b) {
if (b) {
queens[num] = i;
row[i] = 1;
hills[num + i] = 1;
dales[num - i + 2 * n] = 1;
} else {
queens[num] = 0;
row[i] = 0;
hills[num + i] = 0;
dales[num - i + 2 * n] = 0;
}
}
}
public List<List<String>> solveNQueens(int n) {
List<List<String>> lists = new ArrayList<>();
helper(0, new Boolean[n], new Boolean[2 * n], new Boolean[2 * n], new String[n], lists);
return lists;
}
private void helper(int row, Boolean[] col, Boolean[] hills, Boolean[] dales, String[] str, List<List<String>> lists) {
if (row == str.length){
List<String> list = new ArrayList<>();
for (int i = 0 ; i < str.length ; i++) {
list.add(str[i].toString());
}
lists.add(list);
}else{
for (int i = 0; i < str.length; i++) {
int hills_size = 2*str.length - (row + i)-1;
int dales_size = row - i + str.length;
if (col[i]==null&&hills[hills_size]==null&&dales[dales_size]==null){
char[] c = new char[str.length];
Arrays.fill(c,'.');c[i] = 'Q';
str[row] = new String(c);
col[i] =false;hills[hills_size] = false; dales[dales_size] = false;
helper(row+1,col,hills,dales,str,lists);
col[i] = null; hills[hills_size] = null; dales[dales_size] = null;
}
}
}
}