代码随想录刷题学习日记

仅为个人记录复盘学习历程，解题思路来自代码随想录

代码随想录刷题笔记总结网址:
代码随想录

404.左叶子之和

计算给定二叉树的所有左叶子之和。（所有的左边的叶子节点的和）

提供参数：根结点root

关键思路：遍历，判断若为左叶子节点，则将值累加。

主要操作：

递归三要素

1.返回值类型和参数：

参数根结点root，返回值类型为int，需要返回树的左叶子节点的和。

2.终止条件：

如果当前节点为null，返回0；

如果当前节点是叶子节点，返回0；（这是由判断左叶子节点的逻辑决定的）

3.单层递归逻辑：

定义left接收递归左子节点返回的值；

判断左子节点是否为左叶子节点，如果是将值加入left；（这是代码中累加左叶子节点值的逻辑）

判断是否为左叶子节点是通过他的父节点判断，单凭一个节点的属性无法判断它是不是左叶子节点

定义right接收递归右子节点返回的值；

返回left+right；

代码大致如下：

    public int sumOfLeftLeaves(TreeNode root) {
        //终止条件
        //空节点
        if(root==null)return 0;
        //叶节点
        if(root.left==null&&root.right==null)return 0;
        //单层逻辑
        int left=sumOfLeftLeaves(root.left);
        //满足条件加入
        if(root.left!=null&&root.left.left==null&&root.left.right==null)left=root.left.val;
        int right=sumOfLeftLeaves(root.right);
        int sum=left+right;
        return sum;
    }

513.找树左下角的值（递归法）

给定一个二叉树，在树的最后一行找到最左边的值。

提供参数：根结点root

关键思路：前序遍历+回溯。在前序遍历过程中，如果遇到深度更大的就更新结果（深度最大的一定是最后一行），使用前序遍历的目的是确保找到的结果是最左边的值。前序遍历的顺序为：中，左，右，在遍历是如果是同一深度，则先遍历到最左边的，在同一深度的情况下遍历到右边的结果无法覆盖左边的，如果右边结果覆盖左边，说明右边深度更大，说明左边不是最后一行。

主要操作：

递归三要素

1.返回值类型和参数：

需要参数根结点root，还有深度dep，返回值类型为空。

2.终止条件：

完成函数即终止。

3.单层逻辑：

对当前递归层次的节点判断深度是否大于最大深度max，如果大于则更新结果，更新最大深度。

对当前节点的左子树进行遍历。

对当前节点的右子树进行遍历。

代码大致如下：

    public int findBottomLeftValue(TreeNode root) {
        findBL(root,1);
        return res;
    }
    public int maxdep;
    public int res;
    public void findBL(TreeNode node,int dep){
        //

        if(dep>maxdep){
            res=node.val;
            maxdep=dep;
        }
        if(node.left!=null){
            dep++;
            findBL(node.left,dep);
            dep--;
        }
        if(node.right!=null){
            dep++;
            findBL(node.right,dep);
            dep--;
        }
        
    }

如果使用层序遍历不使用递归更简单，在遍历时，将每层第一个元素加入到结果res中，最后循环结束时res中保存的就是最后一层最左边的节点。