学习目标：

每天复习代码随想录上的题目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);
    }
}