学习目标:
每天复习代码随想录上的题目1-2道算法(时间充足可以继续)
今日碎碎念:
1)昨天赶飞机,哎飞机延误,通宵到的学校,太痛苦啦
2)保持打卡!加油啦!
3)今天要做的事情就是,完成算法打卡,然后总结实习的工作,整理好自己的思路,应对后面可能的面试。
力扣刷题
算法
力扣222:222. 完全二叉树的节点个数
bfs做法
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
Deque<TreeNode> que = new LinkedList<>();
int count = 0;
que.offer(root);
while(!que.isEmpty()){
int size = que.size();
for(int i = 0;i<size;i++){
TreeNode tmp = que.poll();
count++;
if(tmp.left!=null) que.offer(tmp.left);
if(tmp.right!=null) que.offer(tmp.right);
}
}
return count;
}
}
力扣110:110. 平衡二叉树
解答思路:
1)这道题更适合使用递归来做
2)首先得明确定义,什么是平衡二叉树?
2.1)是二叉排序树
2.2)任何一个节点的左子树或者右子树都是「平衡二叉树」(左右高度差小于等于 1)
3)这道题更适合我们去通过后序遍历的方式,即从叶子开始往回退,而不要从根节点往下找去判断
class Solution {
public boolean isBalanced(TreeNode root) {
return getHeight(root) == -1 ? false : true;
}
public int getHeight(TreeNode root){
if(root == null) return 0;
int leftHight = getHeight(root.left);
if(leftHight == -1) return -1;
int rightHeight = getHeight(root.right);
if(rightHeight == -1) return -1;
return Math.abs(leftHight-rightHeight) > 1 ? -1 : 1 + Math.max(leftHight,rightHeight);
}
}
力扣257:257. 二叉树的所有路径
解答思路:看注释即可
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();//结果集
if(root == null) return res;
List<Integer> paths = new ArrayList<>();
back(root,paths,res);
return res;
}
public void back(TreeNode root,List<Integer> paths,List<String> res){
//先加入节点
paths.add(root.val);
//判断是否为叶子
if(root.left == null && root.right == null){
//是叶子就直接加入结果集
StringBuilder sb = new StringBuilder();
//开始拼接:注意,最后一个没有箭头,要特殊处理
for(int i = 0;i<paths.size()-1;i++){
//取出数字然后拼接箭头
sb.append(paths.get(i)).append("->");
}
//把最后一个节点加入
sb.append(paths.get(paths.size()-1));
//将本次路径加入结果集
res.add(sb.toString());
}
//如果没到叶子结点,就找左右孩子
if(root.left!=null){
back(root.left,paths,res);
//回溯
paths.remove(paths.size()-1);
}
if(root.right!=null) {
back(root.right,paths,res);
//回溯
paths.remove(paths.size()-1);
}
}
}
力扣404:404. 左叶子之和
解答思路:看注释即可
class Solution {
int sum = 0;
public int sumOfLeftLeaves(TreeNode root) {
dfs(root);
return sum;
}
public void dfs(TreeNode root){
if(root==null){
return;
}
//只要加左节点值,同时需要判断左节点是否还有孩子,没有则加
if(root.left!=null&&root.left.left==null&&root.left.right==null){
sum+=root.left.val;
}
//左右找
dfs(root.left);
dfs(root.right);
}
}