21-01 月份刷题记录
01-01
// 解法一: 跳两格
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
// 如果当前值为1, i每次加2
// 如果当前值为0, 如果下一个值为0, 则 n-- (特判: 当前值为最后一个数时)
for(int i = 0; i < flowerbed.length; i += 2) {
if(flowerbed[i] == 0) {
if(i == flowerbed.length - 1 || flowerbed[i + 1] == 0) {
n --;
} else {
// 提前进入下一个1
i ++;
}
}
}
return n <= 0;
}
}
// 解法二: 暴力遍历
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
for(int i=0; i<flowerbed.length; i++) {
if(flowerbed[i] == 0 && (i == 0 || flowerbed[i-1] == 0) && (i == flowerbed.length-1 || flowerbed[i+1] == 0)) {
n--;
if(n <= 0) return true;
flowerbed[i] = 1;
}
}
return n <= 0;
}
}
知识背景:
二叉搜索树: 左节点的所有值一定小于右节点所有值, 高度相差不超过1
中序遍历: 左 -> 中 -> 右
前序遍历: 中 -> 左 -> 右
后序遍历: 左 -> 右 -> 中
解题思路:
利用递归整理二叉树, 每次以中心为根, 左半部分为左子树, 右半部分为右子树. 先分别递归建立左子树和右子树, 然后令根节点的指针分别指向两棵子树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
// 主要思路:
// 1. 确定根节点为数组中间值
// 2. 递归构造左右子树
// 3. 维护根节点和左右子树之间的关系
return build(0, nums.length - 1, nums);
}
public TreeNode build(int l, int r, int[] nums) {
if(l > r) return null;
int mid;
mid = (l + r) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = build(l, mid - 1, nums);
root.right = build(mid + 1, r, nums);
return root;
}
}
利用递归方法比较简单, 具体代码如下
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
// 递归做法
frontPrint(root, list);
return list;
// 非递归做法
}
public void frontPrint(TreeNode root, List<Integer> list) {
if(root == null) {
return;
}
list.add(root.val);
frontPrint(root.left, list);
frontPrint(root.right, list);
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
mediumPrint(root, list);
return list;
}
public void mediumPrint(TreeNode root, List<Integer> list) {
if(root == null) {
return ;
}
mediumPrint(root.left, list);
list.add(root.val);
mediumPrint(root.right, list);
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
mediumPrint(root, list);
return list;
}
public void mediumPrint(TreeNode root, List<Integer> list) {
if(root == null) {
return ;
}
mediumPrint(root.left, list);
mediumPrint(root.right, list);
list.add(root.val);
}
}
后面会发表如何利用非递归方法实现上述三种遍历