前言

经过数模比赛的四天忙碌后博主继续开始LeetCode学习了，给大家分享学习心路的同时也是在不断勉励自己每天把自己的学的东西去进行一个产出记录，不足的地方欢迎大家批评指正， 一起加油吧朋友们！💪💪💪

左叶子之和

LeetCode题目链接

给定二叉树的根节点root要求返回所有左叶子之和

首先要明确左叶子的概念。🤔🤔🤔由下图可以看出，判断一个节点是不是左叶子是要根据其父结点来判断的，即节点的左节点不为空，然后呢节点的左节点的左节点为空，节点的左节点的右节点也为空，则说明找到了一个左叶子，这也是我们递归单层处理逻辑的核心一步✨✨✨。

1727356368761

递归三要素如下：

1
private int sumOfLeftNodes(TreeNode root){}//参数为以root为根节点的子树，返回值即为左叶子的和
1
2
if(root == null){return 0;}
if(root.left == null && root.right == null){return 0;} //左边为叶子
1
2
3
4
5

if(root.left != null && root.left.left == null && root.left.right == null){ //遇到左叶子进行求和
	return root.left.val + sumOfLeftNodes(root.right);
}
return sumOfLeftNodes(root.right) + sumOfLeftNodes(root.right);//没遇到则两边找

完整代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){return 0;}
        return sumOfLeftNodes(root);
    }

    private int sumOfLeftNodes(TreeNode root){
        if(root == null){return 0;}
        if(root.left == null && root.right == null){return 0;}

        if(root.left != null && root.left.left == null && root.left.right == null){
            return root.left.val + sumOfLeftNodes(root.right);
        }
        return sumOfLeftNodes(root.left) + sumOfLeftNodes(root.right);
        
    }
}

接着来处理迭代的情况，我们用栈来进行数据保存，遇到左叶子进行弹栈求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**迭代法 */
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){return 0;}
        Stack<TreeNode> stack = new Stack<>(); //用栈存递归节点
        stack.push(root);
        int result = 0; //用整型变量存递归求和变量
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            if(cur.left != null && cur.left.left == null && cur.left.right == null){
                //找到左叶子
                result += cur.left.val;

            }
            if(cur.right != null){stack.push(cur.right);}
            if(cur.left != null){stack.push(cur.left);} //要优先处理左节点就得先把右节点压栈
        }
        return result;
    } 
}

找树左小角的值

LeetCode题目链接

给定一个二叉树的根节点root，请找出该二叉树的 最底层 最左边 节点的值。

我们先梳理思路，首先肯定是层序遍历会比较简单，而递归的话就是递归遍历到最后一层对吧，找最左边节点的话我们就保持最左优先处理即可，那怎么判断到最后一层了呢？计算深度，深度最大的节点一定是最后一行的节点。🤔🤔🤔

1727359299087

我们来一起确定下递归三要素

1
2
3
4
5
6
7
//首先要计算深度需要一个记录最大的变量和一个记录现在遍历到节点的深度，一个为全局变量一个为入参
//然后还需要一个值来保存找到的最左边节点的值，可以为入参也可以为全局变量
//当然树的根节点也要传入
//用全局变量来记录最左边节点的值
int Depth = -1;
int val = 0; //初始化
private void findLeftNodeVal(TreeNode root, int depth){}
1
2
3
4
5
6
7
if(root == null){return;}//递归到最底层
if(root.left == null && root.right == null){ //找到一个最左边的节点，是不是最后一层不知道
	if(Depth < depth){ //当前节点的更深
		val = root.val;
		Depth = depth;//更新
	}
}
1
2
if(root.left != null){findLeftNodeVal(root.left, depth + 1);}//优先往左递归
if(root.right != null){findLeftNodeVal(root.right, depth + 1);}

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 /**递归法 */
class Solution {

    private int Depth = -1;
    private int val = 0;

    public int findBottomLeftValue(TreeNode root) {
        val = root.val; //题目中说节点个数大于等于1
        findLeftNodeVal(root, 1); 
        return val;
    }

    private void findLeftNodeVal(TreeNode root, int depth){
        if(root == null){return;}//递归到最底层
        if(root.left == null && root.right == null){ //找到一个最左边的节点，是不是最后一层不知道
            if(Depth < depth){ //当前节点的更深
                val = root.val;
                Depth = depth;//更新
            }
        }
        if(root.left != null){findLeftNodeVal(root.left, depth + 1);}//优先往左递归
        if(root.right != null){findLeftNodeVal(root.right, depth + 1);}
    }
}

接着来处理迭代的情况，使用层序遍历，每行只用判断第一个节点的值即可，用队列来存储遍历的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**迭代法 层序遍历 只记录每行的第一个节点的值即可 */
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int result = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode cur = queue.poll();
                if(i == 0){  //只判断一个
                    result = cur.val;
                }
                if(cur.left != null){queue.offer(cur.left);}
                if(cur.right != null){queue.offer(cur.right);}
            }
        }
        return result;
    }
}

下图为双端队列的两端出入队的方法，因为比较容易混淆🤔🤔🤔

1727361617726

除了出入队，还有两端元素的查看操作，这里的话peek和get有一些差别，peek方法 查看元素但不抛出异常，如果队列为空则返回null，而get方法 查看元素，但如果队列为空会抛出异常，这点也容易混淆🤔🤔🤔

1727362173113

总结

今天就到这里啦，保安在赶人了，明天继续加油！！✊✊✊