代码随想录day14 二叉树（2）

标签：TreeNode val int 随想录 day14 二叉树 null 节点 left

文章目录

• • day11 栈与队列(2)
  • • 栈与队列的总结
  • day13 二叉树（1）
  • day14 二叉树（2）

day11 栈与队列(2)

150. 逆波兰表达式求值

https://leetcode.cn/problems/evaluate-reverse-polish-notation/

逆波兰表达式，也就是后缀表达式，所谓后缀就是指运算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
• 适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。

例：( 1 + 2 ) * ( 3 + 4 )

遇见数字1，2就放入栈，遇到运算符+,就把栈里数据1，2取出用运算符+，结果3再加入栈里。继续操作，遇到3，4放入栈，遇到运算符+，取出3，4，运算符+结果是7，放入栈。遇到运算符*，取出3，7，运算结果是21，放入栈。

我们在输入合法的情况下写函数，不考虑输入非法情况。

class Solution {
    public int evalRPN(String[] tokens) {
        //虽然 Java 提供了一个 Stack 类，但推荐使用 Deque 接口来实现栈的功能，因为 Deque 提供了更多的灵活性和更好的性能。
        // 初始化了一个双端队列，用LiskedList实现
        Deque<Integer> stack =new LinkedList();
        //遍历数组
        for(String s: tokens){
            //处理加法操作符
            if("+".equals(s)){
                stack.push(stack.pop()+stack.pop());
            }else if("-".equals(s)){
                int num1=stack.pop();
                int num2=stack.pop();
                //先出来的是减数，后出来的是被减数
                stack.push(num2-num1);
            }else if("*".equals(s)){
                stack.push(stack.pop()*stack.pop());
            }else if("/".equals(s)){
                int num1=stack.pop();
                if(num1==0){
                    throw new ArithmeticException("Division by zero");
                }
                int num2=stack.pop();
                //先弹出的是除数，再弹出的是被除数
                stack.push(num2/num1);
            }else{
                //如果当前是数字，将其转换为Integer后压入栈
                stack.push(Integer.valueOf(s));
            }
        }
        //栈里唯一一个元素就是答案
        return stack.pop();
    }
}

239. 滑动窗口最大值

https://leetcode.cn/problems/sliding-window-maximum/

单调栈的过程pop() push() getMaxValue()

确保出口处的元素的最大值，把小数弹出。像这个例题，直接把1弹出去，留下3，没必要维护比3之前小的元素。

如果pop()的是当前元素最大值3，此时窗口[3,-1,-3]，pop(3)，push(5)，5比-1和-3大。5放出口处。

1 自定义双端队列 MyQueue：

• poll(int val) 方法：弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出。同时判断队列当前是否为空。
• add(int val) 方法：添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出，保证队列元素单调递减。
• peek() 方法：返回队列队顶元素，即当前窗口的最大值。

2 Solution 类和 maxSlidingWindow 方法：

• 初始化结果数组：int len = nums.length - k + 1; 计算结果数组的长度。
• 初始化自定义队列：MyQueue myQueue = new MyQueue();
• 处理前 k 个元素：将前 k 个元素加入队列。
• 滑动窗口处理：
  • 移除窗口最前面的元素。
  • 加入窗口最后面的元素。
  • 记录当前窗口的最大值。

class MyQueue{
    //自定义的双端队列 MyQueue
    Deque<Integer> deque=new LinkedList<>();

    //弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出
    void poll(int val){
        //当然，当前队列不能为空
        if(!deque.isEmpty()&&val==deque.peek()){
            deque.poll();
        }
    }

    //添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出，保证队列元素单调递减。
    void add(int val){
        while(!deque.isEmpty()&&val>deque.getLast()){
            deque.removeLast();
        }
        deque.add(val);
    }

    //返回队列队顶元素，即当前窗口的最大值。
    int peek(){
        return deque.peek();
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //原数组为空，窗口大小为0，返回空数组
        if(nums==null||nums.length==0||k==0){
            return new int[0];
        }
        //原数组长度为1
        if(nums.length==1){
            return nums;
        }
        //初始化结果数组
        int len=nums.length-k+1;
        int[] result=new int[len];
        //记录result中存储位置，作为索引位置来存储每次滑动窗口的最大值
        int num=0;
        MyQueue myQueue=new MyQueue();

        //将前k个元素放入队列
        for(int i=0;i<k;i++){
            myQueue.add(nums[i]);
        }
        result[num]=myQueue.peek();
        num++;

        //处理剩余的元素
        for(int i=k;i<nums.length;i++){
            //滑动窗口移除最前面的元素
            myQueue.poll(nums[i-k]);
            //滑动串口加入最后面的元素
            myQueue.add(nums[i]);
            //记录当前窗口的最大值
            result[num]=myQueue.peek();
            num++;
        }
        return result;
    }
}

347 前 K 个高频元素

https://leetcode.cn/problems/top-k-frequent-elements/descriptio

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2

输出: [1,2]

示例 2:

输入: nums = [1], k = 1

输出: [1]

统计频率

• 使用HashMap统计每个元素的出现次数。

解法1：基于大顶堆

• 创建一个大顶堆，存储元素及其出现次数。
• 将所有元素加入大顶堆。
• 从大顶堆中取出前 k 个元素。

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //大顶堆
        //边界条件处理
        if(nums==null||nums.length==0||k==0){
            return new int[0];
        }
        if(k==nums.length){
            return nums;
        }
        //初始化HashMap，统计频次
        Map<Integer,Integer> map=new HashMap<>();
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        //创建大顶堆
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair2[1] - pair1[1]);
        //将所有元素加入大顶堆
        for(Map.Entry<Integer,Integer> entry :map.entrySet()){
            pq.add(new int[]{entry.getKey(),entry.getValue()});
        }
        //从大顶堆中取出前k个元素
        int[] ans=new int[k];
        for(int i=0;i<k;i++){
            ans[i]=pq.poll()[0];
        }
        return ans;
    }
}

解法2：基于小顶堆

• 创建一个小顶堆，存储元素及其出现次数。
• 维护一个小顶堆，使其最多包含 k 个元素。
• 如果当前元素的出现次数大于小顶堆的根结点（出现次数最少的元素），则替换掉根结点。
• 最后从小顶堆中取出所有元素。

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    // 解法2：基于小顶堆实现
    public int[] topKFrequent2(int[] nums, int k) {
        // 边界条件处理
        if (nums == null || nums.length == 0 || k == 0) {
            return new int[0]; // 输入数组为空或长度为0，或者k为0，直接返回空数组
        }
        if (k == nums.length) {
            return nums; // 如果k等于nums的长度，直接返回nums数组
        }

        // 初始化 HashMap，统计频次
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1); // 统计每个元素的出现次数
        }

        // 创建小顶堆
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);
        // 遍历 HashMap 中的所有条目
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (pq.size() < k) { // 小顶堆元素个数小于k个时直接加入
                pq.add(new int[]{entry.getKey(), entry.getValue()});
            } else {
                if (entry.getValue() > pq.peek()[1]) { // 当前元素的出现次数大于小顶堆的根结点（出现次数最少的那个）
                    pq.poll(); // 弹出队头（小顶堆的根结点），即把堆里出现次数最少的那个删除
                    pq.add(new int[]{entry.getKey(), entry.getValue()}); // 将当前元素加入小顶堆
                }
            }
        }

        // 从大顶堆中取出前 k 个元素
        int[] ans = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            ans[i] = pq.poll()[0]; // 依次从队头弹出元素，存入结果数组
        }

        return ans; // 返回结果数组
    }
}

栈与队列的总结

一 栈与队列的理论基础

1. Java 中 Stack 和 Queue 是容器吗？

Stack 和 Queue 是容器适配器，它们依赖于底层的具体容器来实现功能。

2. 我们使用的 JDK 中 Stack 和 Queue 是如何实现的？

• Stack 类继承自 Vector，因此它是一个线程安全的动态数组。
• Queue 接口有多个实现类，如 LinkedList、PriorityQueue 等。LinkedList 实现了 Deque 接口，可以作为双端队列使用。

3. Stack 和 Queue 提供迭代器来遍历空间吗？

• Stack 和 Queue 都提供了迭代器来遍历元素。Stack 继承自 Vector，因此可以直接使用 Vector 的迭代器。Queue 的实现类如 LinkedList 也提供了迭代器。

栈内元素在内存中是否连续分布？

• 陷阱1：栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中不一定是连续分布的。
• 陷阱2：默认情况下，Stack 底层使用 Vector，数据在内存中是连续分布的。但如果是自定义的栈，底层容器不同，数据分布也可能不同。

二 栈经典题目

（1）栈在系统中的应用

1. 括号匹配问题：

使用栈来匹配括号，确保括号的正确嵌套。

示例代码：

import java.util.Stack;

public class ParenthesesMatcher {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

2. 字符串去重问题：

使用栈来去除字符串中的相邻重复项。

import java.util.Stack;

public class RemoveDuplicates {
    public String removeDuplicates(String S) {
        Stack<Character> stack = new Stack<>();
        for (char c : S.toCharArray()) {
            if (!stack.isEmpty() && stack.peek() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
}

3. 逆波兰表达式问题：

使用栈来计算逆波兰表达式。

import java.util.Stack;

public class EvaluateReversePolishNotation {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if (isOperator(token)) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(applyOp(a, b, token));
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }

    private boolean isOperator(String token) {
        return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");
    }

    private int applyOp(int a, int b, String op) {
        switch (op) {
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            case "/": return a / b;
            default: throw new IllegalArgumentException("Invalid operator");
        }
    }
}

（2）队列的经典题目

1. 滑动窗口最大值问题

使用单调队列来解决滑动窗口最大值问题。

import java.util.Deque;
import java.util.LinkedList;

public class SlidingWindowMaximum {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k == 0) {
            return new int[0];
        }
        Deque<Integer> deque = new LinkedList<>();
        int[] result = new int[nums.length - k + 1];

        for (int i = 0; i < nums.length; i++) {
            // 移除不在窗口范围内的元素
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            // 移除小于当前元素的元素
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);

            // 当窗口达到指定大小时，记录当前窗口的最大值
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }
}

2. 求前 K 个高频元素

使用优先级队列（大顶堆或小顶堆）来求前 K 个高频元素。

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class TopKFrequentElements {
    public int[] topKFrequent(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k == 0) {
            return new int[0];
        }
        if (k == nums.length) {
            return nums;
        }

        // 统计每个元素的出现次数
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 创建小顶堆
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);

        // 将所有元素加入小顶堆
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (pq.size() < k) {
                pq.add(new int[]{entry.getKey(), entry.getValue()});
            } else {
                if (entry.getValue() > pq.peek()[1]) {
                    pq.poll();
                    pq.add(new int[]{entry.getKey(), entry.getValue()});
                }
            }
        }

        // 从大顶堆中取出前 k 个元素
        int[] ans = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            ans[i] = pq.poll()[0];
        }

        return ans;
    }
}

总结

在栈与队列系列中，我们强调了栈与队列的基础知识，包括它们的底层实现和常见应用场景。通过具体的题目练习，我们可以更好地理解和掌握这些数据结构的使用方法。

1. 栈与队列的基础：

• 栈和队列是常见的数据结构，栈遵循后进先出（LIFO）原则，队列遵循先进先出（FIFO）原则。
• 栈和队列可以通过不同的底层容器实现，如 Vector、LinkedList 等。

2. 栈的应用：

• 括号匹配：使用栈来匹配括号，确保括号的正确嵌套。
• 字符串去重：使用栈来去除字符串中的相邻重复项。
• 逆波兰表达式：使用栈来计算逆波兰表达式。

3. 队列的应用：

• 滑动窗口最大值：使用单调队列来解决滑动窗口最大值问题。
• 前 K 个高频元素：使用优先级队列（大顶堆或小顶堆）来求前 K 个高频元素。

day13 二叉树（1）

---

关于二叉树的拾到入门题

---

144 二叉树的前序遍历144. 二叉树的前序遍历

前序遍历的顺序是：访问根节点 -> 访问左子树 -> 访问右子树

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出：[1,2,4,5,6,7,3,8,9]

/**
 * 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> result=new ArrayList<>();
        preorderHelper(root,result);
        return result;
    }
    private void preorderHelper(TreeNode node,List<Integer> result){
        if(node==null){
            return;
        }
        //访问根节点
        result.add(node.val);
        //访问左子树,右子树
        preorderHelper(node.left,result);
        preorderHelper(node.right,result);
    }
}

145 二叉树的后序遍历 145. 二叉树的后序遍历

后序遍历的顺序是：访问左子树 -> 访问右子树 -> 访问根节点

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出：[4,6,7,5,2,9,8,3,1]

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<>();
        
        return result;
    }
    private void postorderHelper(TreeNode node,List<Integer> result){
        if(node==null){
            return null;
        }
        postorderHelper(node.left,result);
        postorderHelper(node.right,result);
        result.add(node.val);
    }
}

94. 二叉树的中序遍历 94. 二叉树的中序遍历

中序遍历的顺序是：访问左子树 -> 访问根节点 -> 访问右子树

输入：root = [1,null,2,3]

输出：[1,3,2]

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorderHelper(root, result);
        return result;
    }
    private void inorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        inorderHelper(node.left, result); 
        result.add(node.val); 
        inorderHelper(node.right, result);
    }
}

102 二叉树的层序遍历 102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

/**
 * 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<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result=new ArrayList<>();
        if(root==null){
            return result;
        }
        //将根节点加入队列
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        //队列不为空，遍历队列
        while(!queue.isEmpty()){
            //获取当前层的节点数量
            int levelSize= queue.size();
            //创建一个列表来存储当前层的节点值
            List<Integer> currentLevel=new ArrayList<>();
            //遍历当前层的所有节点
            for(int i=0;i<levelSize;i++){
                //弹出一个节点，添加到当前层的列表中
                TreeNode node=queue.poll();
                currentLevel.add(node.val);
                 //该节点有左子节点,将其加入队列
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            //将当前层的列表添加到结果列表中
            result.add(currentLevel);
        }
        //返回结果列表
        return result;
    }
}

1. 初始化：

创建一个结果列表 result，用于存储每一层的节点值。

如果根节点 root 为 null，直接返回空的结果列表。

2. 队列初始化：

使用队列 queue 来存储待访问的节点，初始时将根节点加入队列。

3. 层次遍历：

使用一个 while 循环，当队列不为空时，表示还有节点未被访问。

获取当前层的节点数量 levelSize。

创建一个列表 currentLevel，用于存储当前层的节点值。

使用一个 for 循环，遍历当前层的所有节点：

• 从队列中弹出一个节点，并将其值添加到 currentLevel 列表中。
• 如果该节点有左子节点，将左子节点加入队列。
• 如果该节点有右子节点，将右子节点加入队列。

将 currentLevel 列表添加到结果列表 result 中。

107 二叉树的层序遍历 II 107. 二叉树的层序遍历 II

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

/**
 * 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<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result=new ArrayList<>();
        if(root==null){
            return result;
        }
        //将跟节点加入队列
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        //队列不为空，遍历队列
        while(!queue.isEmpty()){
            //获取当前层的节点数量
            int levelSize=queue.size();
            //创建一个列表来存储当前层的节点值
            List<Integer> currentLevel=new ArrayList<>();
            //遍历当前层的所有节点
            for(int i=0;i<levelSize;i++){
                //弹出一个节点，添加到当前层的列表中
                TreeNode node=queue.poll();
                currentLevel.add(node.val);
                //该节点有左子节点,将其加入队列
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }  
            }
            result.add(currentLevel);
        }
        //反转结果列表，使其从叶子节点所在层到根节点所在的层
        Collections.reverse(result);
        return result;
    }
}

199. 二叉树的右视图199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

例1：
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
例2：
输入: [1,null,3]
输出: [1,3]

层序遍历（广度优先搜索 BFS）实现

/**
 * 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> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result; // 如果根节点为空，直接返回空的结果列表
        }
        //初始化队列，将根节点加入队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root); 
        //层次遍历
        while(!queue.isEmpty()){
            //获取当前层的节点数量
            int levelSize=queue.size();
            for(int i=0;i<levelSize;i++){
                //从队列中弹出一个节点
                TreeNode node=queue.poll();
                if(i==levelSize-1){
                    //添加当前层最后一个节点的值
                    result.add(node.val);
                }
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
        }
        return result;
    }
}

• 使用一个 <font style="color:rgb(44, 44, 54);">while</font> 循环，当队列不为空时，表示还有节点未被访问。
• 获取当前层的节点数量 <font style="color:rgb(44, 44, 54);">levelSize</font>。
• 使用一个 <font style="color:rgb(44, 44, 54);">for</font> 循环，遍历当前层的所有节点：
  • 从队列中弹出一个节点。
  • 如果当前节点是当前层的最后一个节点，将其值添加到结果列表 <font style="color:rgb(44, 44, 54);">result</font> 中。
  • 如果该节点有左子节点，将左子节点加入队列。
  • 如果该节点有右子节点，将右子节点加入队列。

637. 二叉树的层平均值 637. 二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。

/**
 * 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<Double> averageOfLevels(TreeNode root) {
        List<Double> result=new ArrayList<>();
        if(root==null){
            return result;
        }
        //队列初始化, 将根节点加入队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        //层次遍历,当队列不为空时，继续遍历
        while(!queue.isEmpty()){
            // 获取当前层的节点数量
            int levelSize=queue.size();
            double sum=0.0;
            // 遍历当前层的所有节点
            for(int i=0;i<levelSize;i++){
                // 从队列中弹出一个节点,累加当前层的节点值
                TreeNode node = queue.poll();
                sum+=node.val;

                if(node.left!=null){
                    queue.offer(node.right);
                }
                if(node.right!=null){
                    queue.offer(node.left);
                }
            }
            // 计算当前层的平均值
            double average=sum/levelSize;
            result.add(average);
        }
        return result;
    }
}

层次遍历:

• 使用一个 <font style="color:rgb(44, 44, 54);">while</font> 循环，当队列不为空时，表示还有节点未被访问。
• 获取当前层的节点数量 <font style="color:rgb(44, 44, 54);">levelSize</font>。
• 初始化当前层节点值的总和 <font style="color:rgb(44, 44, 54);">sum</font>。
• 使用一个 <font style="color:rgb(44, 44, 54);">for</font> 循环，遍历当前层的所有节点：
  • 从队列中弹出一个节点。
  • 累加当前层的节点值。
  • 如果该节点有左子节点，将左子节点加入队列。
  • 如果该节点有右子节点，将右子节点加入队列。
• 计算当前层的平均值，并将其添加到结果列表 <font style="color:rgb(44, 44, 54);">result</font> 中。

429.N叉树的层序遍历429. N 叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

N叉树的层序遍历类似于二叉树的层序遍历，但每个节点可以有多个子节点。

1. 初始化：
   • 创建一个结果列表 <font style="color:rgb(44, 44, 54);">result</font>，用于存储每一层的节点值。
   • 如果根节点 <font style="color:rgb(44, 44, 54);">root</font> 为 <font style="color:rgb(44, 44, 54);">null</font>，直接返回空的结果列表。
2. 队列初始化：
   • 使用队列 <font style="color:rgb(44, 44, 54);">queue</font> 来存储待访问的节点，初始时将根节点加入队列。
3. 层次遍历：
   • 使用一个 <font style="color:rgb(44, 44, 54);">while</font> 循环，当队列不为空时，表示还有节点未被访问。
   • 获取当前层的节点数量 <font style="color:rgb(44, 44, 54);">levelSize</font>。
   • 创建一个列表 <font style="color:rgb(44, 44, 54);">currentLevel</font>，用于存储当前层的节点值。
   • 使用一个 <font style="color:rgb(44, 44, 54);">for</font> 循环，遍历当前层的所有节点：
     • 从队列中弹出一个节点。
     • 将节点的值添加到 <font style="color:rgb(44, 44, 54);">currentLevel</font> 列表中。
     • 如果该节点有子节点，将所有子节点加入队列。
   • 将 <font style="color:rgb(44, 44, 54);">currentLevel</font> 列表添加到结果列表 <font style="color:rgb(44, 44, 54);">result</font> 中。
4. 返回结果：

返回结果列表 <font style="color:rgb(44, 44, 54);">result</font>，其中包含每一层的节点值。

/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;

public Node() {}

public Node(int _val) {
    val = _val;
}

public Node(int _val, List<Node> _children) {
    val = _val;
    children = _children;
}
};
*/

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        // 1 结果初始化，根节点临界情况
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        // 2 队列初始化，将根节点加入队列
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        // 3 层次遍历
        while (!queue.isEmpty()) {
            // 获取当前层的节点数量
            int levelSize = queue.size();
            // 创建一个列表来存储当前层的节点值
            List<Integer> currentLevel = new ArrayList<>();

            // 遍历当前层所有节点，队列中弹出一个节点添加到当前层列表中
            for (int i = 0; i < levelSize; i++) {
                Node node = queue.poll();
                currentLevel.add(node.val);

                // 如果该节点有子节点，将当前节点的所有子节点加入队列
                if (node.children != null) {
                    for (Node child : node.children) {
                        queue.offer(child);
                    }
                }
            }
            // 将当前层的列表添加到结果列表中
            result.add(currentLevel);
        }
        return result;
    }
}

515. 在每个树行中找最大值 515. 在每个树行中找最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]

层序遍历（广度优先搜索 BFS）来实现

/**
 * 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> largestValues(TreeNode root) {
        List<Integer> result=new ArrayList<>();
        if(root==null){
            return result;
        }

        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int levelSize=queue.size();
            int maxVal=Integer.MIN_VALUE;

            for(int i=0;i<levelSize;i++){
                TreeNode node=queue.poll();
                maxVal=Math.max(maxVal,node.val);

                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            //将该层最大值添加到结果列表
            result.add(maxVal);
        }
        return result;
    }
}

层次遍历

• 使用一个 <font style="color:rgb(44, 44, 54);">while</font> 循环，当队列不为空时，表示还有节点未被访问。
• 获取当前层的节点数量 <font style="color:rgb(44, 44, 54);">levelSize</font>。
• 初始化当前层的最大值 <font style="color:rgb(44, 44, 54);">maxVal</font>。
• 使用一个 <font style="color:rgb(44, 44, 54);">for</font> 循环，遍历当前层的所有节点：
  • 从队列中弹出一个节点。
  • 更新当前层的最大值。
  • 如果该节点有左子节点，将左子节点加入队列。
  • 如果该节点有右子节点，将右子节点加入队列。
• 将当前层的最大值添加到结果列表 <font style="color:rgb(44, 44, 54);">result</font> 中。

116. 填充每个节点的下一个右侧节点指针116. 填充每个节点的下一个右侧节点指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
    int val;
    Node *left;
    Node *right;
    Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if(root==null){
            return null;
        }
        //使用leftmost指针指向当前层的第一个节点。
        Node leftmost=root;
        while(leftmost.left!=null){
            
            Node head=leftmost;
           
            while(head!=null){
                //连接当前节点的两个子节点
                head.left.next = head.right;

                //将右子节点连接到下一个节点的左子节点
                if(head.next!=null){
                head.right.next=head.next.left;
            }
            //移动到当前层的下一个节点
            head=head.next;
            }
            //移动到下一层
            leftmost=leftmost.left;
        }
        return root;
    }
}

• 使用 <font style="color:rgb(44, 44, 54);">leftmost</font> 指针指向当前层的第一个节点。
• 使用一个 <font style="color:rgb(44, 44, 54);">while</font> 循环，当 <font style="color:rgb(44, 44, 54);">leftmost.left</font> 不为 <font style="color:rgb(44, 44, 54);">null</font> 时，表示还有下一层。
• 使用 <font style="color:rgb(44, 44, 54);">head</font> 指针遍历当前层的所有节点：
  • 将当前节点的左子节点的 <font style="color:rgb(44, 44, 54);">next</font> 指针指向右子节点。
  • 如果当前节点的 <font style="color:rgb(44, 44, 54);">next</font> 指针不为 <font style="color:rgb(44, 44, 54);">null</font>，将当前节点的右子节点的 <font style="color:rgb(44, 44, 54);">next</font> 指针指向下一节点的左子节点。
  • 移动 <font style="color:rgb(44, 44, 54);">head</font> 指针到下一节点。
• 移动 <font style="color:rgb(44, 44, 54);">leftmost</font> 指针到下一层的第一个节点。

117. 填充每个节点的下一个右侧节点指针 II117. 填充每个节点的下一个右侧节点指针 II

给定一个二叉树：

struct Node {
    int val;
    Node *left;
    Node *right;
    Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

与之前的完美二叉树不同，这次的二叉树可能不是完美的，也就是说，某些节点可能没有两个子节点。

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if(root==null){
            return null;
        }
        Node start=root;
        while(start!=null){
            //使用虚拟头节点
            Node dummy=new Node(0);
            Node current=dummy;

            while(start!=null){
                if(start.left!=null){
                    // 将当前节点的左子节点连接到当前指针的 next,移动当前指针到左子节点
                    current.next=start.left;
                    current=current.next;
                }
                if (start.right != null) {
                    // 将当前节点的右子节点连接到当前指针的 next,移动当前指针到右子节点
                    current.next = start.right;
                    current = current.next;
                }
                // 移动到当前层的下一个节点
                start=start.next;
            }
            // 移动到下一层的第一个节点
            start=dummy.next;
        }
        return root;
    }
}

• 使用 <font style="color:rgb(44, 44, 54);">start</font> 指针指向当前层的第一个节点。
• 使用一个 <font style="color:rgb(44, 44, 54);">while</font> 循环，当 <font style="color:rgb(44, 44, 54);">start</font> 不为 <font style="color:rgb(44, 44, 54);">null</font> 时，表示还有当前层的节点需要处理。
• 使用 <font style="color:rgb(44, 44, 54);">dummy</font> 节点作为虚拟头节点，帮助连接下一层的节点。
• 使用 <font style="color:rgb(44, 44, 54);">current</font> 指针遍历当前层的所有节点：
  • 如果当前节点有左子节点，将 <font style="color:rgb(44, 44, 54);">current.next</font> 指向左子节点，并移动 <font style="color:rgb(44, 44, 54);">current</font> 指针。
  • 如果当前节点有右子节点，将 <font style="color:rgb(44, 44, 54);">current.next</font> 指向右子节点，并移动 <font style="color:rgb(44, 44, 54);">current</font> 指针。
  • 移动 <font style="color:rgb(44, 44, 54);">start</font> 指针到当前节点的下一个节点。
• 移动 <font style="color:rgb(44, 44, 54);">start</font> 指针到下一层的第一个节点，即 <font style="color:rgb(44, 44, 54);">dummy.next</font>。

104. 二叉树的最大深度104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

输入：root = [3,9,20,null,null,15,7]
输出：3
输入：root = [1,null,2]
输出：2

二叉树的最大深度计算。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

/**
 * 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 int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //创建一个队列 queue，并将根节点加入队列。
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            // 当前层的节点数
            int levelSize = queue.size(); 

            for (int i = 0; i < levelSize; i++) {
                // 弹出当前层的一个节点
                TreeNode node = queue.poll(); 
                if (node.left != null) {
                    // 将左子节点加入队列
                    queue.offer(node.left); 
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            // 当前层遍历完后，深度加1
            depth++; 
        }
        return depth;
    }
}

递归法

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 int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left); // 计算左子树的最大深度
        int rightDepth = maxDepth(root.right); // 计算右子树的最大深度
        return Math.max(leftDepth, rightDepth) + 1; // 返回左右子树最大深度加1
    }
}

111. 二叉树的最小深度111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

输入：root = [3,9,20,null,null,15,7]
输出：2

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

/**
 * 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 int minDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        //创建一个队列 queue，并将根节点加入队列 初始化深度 depth 为 1。
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        int depth=1;
        
        while(!queue.isEmpty()){
            // 当前层的节点数
            int levelSize=queue.size();

            for(int i=0;i<levelSize;i++){
                // 弹出当前层的一个节点
                TreeNode node = queue.poll();
                // 如果当前节点是叶子节点，返回当前深度
                if (node.left == null && node.right == null) {
                    return depth;
                }

                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            depth++;
        }
        return depth;
    }
}

层次遍历：

• 使用一个 <font style="color:rgb(44, 44, 54);">while</font> 循环，当队列不为空时，表示还有节点未被访问。
• 获取当前层的节点数 <font style="color:rgb(44, 44, 54);">levelSize</font>。
• 使用一个 <font style="color:rgb(44, 44, 54);">for</font> 循环，遍历当前层的所有节点：
  • 从队列中弹出一个节点，如果当前节点是叶子节点，返回当前深度。
  • 如果该节点有左子节点，将左子节点加入队列。
  • 如果该节点有右子节点，将右子节点加入队列。
• 当前层遍历完后，深度 <font style="color:rgb(44, 44, 54);">depth</font> 加1。

day14 二叉树（2）

226. 翻转二叉树226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

前驱和后驱是方便实现的，中驱有些难。原本的左子树变成右子树，原本的右子树变成左子树。

（1）递归

/**
 * 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 TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        //交换左右子树
        TreeNode temp=root.left;
        root.left=invertTree(root.right);
        root.right=invertTree(temp);

        return root;
    }
}

使用一个临时变量 temp 存储当前节点的左子树。

递归调用 invertTree 方法，将当前节点的右子树赋值给左子树。

再次递归调用 invertTree 方法，将临时变量 temp 中存储的左子树赋值给右子树。

（2）BFS写法

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        //创建一个队列 queue，并将根节点加入队列
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            //从队列中弹出一个节点
            TreeNode node=queue.poll();

            //交换左右子树
            TreeNode temp=node.left;
            node.left=node.right;
            node.right=temp;

            //将左右子节点加入队列,若不为空
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
        }
        return root;
    }
}

101. 对称二叉树101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

输入：root = [1,2,2,3,4,4,3]
输出：true

/**
 * 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 boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        //递归检查对称性,调用辅助方法 isMirror，传入根节点的左子树和右子树
        return isMissor(root.left,root.right);
    }
    private boolean isMissor(TreeNode left,TreeNode right){
        if(left==null&&right==null){
            return true;
        }
        if(left==null||right==null){
            reutrn false;
        }
        if(left.val!=right.val){
            return false;
        }
        //递归检查左子树的左子节点和右子树的右子节点，以及左子树的右子节点和右子树的左子节点。
        reurn isMissor(left.left,right.right) && isMissor(left.right,right.left);
    }
}

BFS方法实现此题

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);

        while(!queue.isEmpty()){
            TreeNode left=queue.poll();
            TreeNode right=queue.poll();

            if(left==null&&right==null){
                continue;
            }
            if(left==null&&right!=null){
                return false;
            }
            if(left!=null&&right==null){
                return false;
            }
            if(left.val!=right.val){
                return false;
            }
            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;
    }
}

104. 二叉树的最大深度

再次理解二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

输入：root = [3,9,20,null,null,15,7]

输出：3

/**
 * 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 int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //创建一个队列 queue，并将根节点加入队列。
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            // 当前层的节点数
            int levelSize = queue.size(); 

            for (int i = 0; i < levelSize; i++) {
                // 弹出当前层的一个节点
                TreeNode node = queue.poll(); 
                if (node.left != null) {
                    // 将左子节点加入队列
                    queue.offer(node.left); 
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            // 当前层遍历完后，深度加1
            depth++; 
        }
        return depth;
    }
}

  //假设我们有一棵如下所示的二叉树
    3
   / \
  9  20
    /  \
   15   7

初始状态
队列 queue： [3]
深度 depth： 0

第一层
当前层的节点数： levelSize = 1
遍历当前层的节点：
弹出节点 3
将节点 3 的左子节点 9 加入队列
将节点 3 的右子节点 20 加入队列
当前层遍历完后，深度加1：
深度 depth： 1
队列 queue： [9, 20]
深度 depth： 1

第二层
当前层的节点数： levelSize = 2
遍历当前层的节点：
弹出节点 9，没有子节点
弹出节点 20
将节点 20 的左子节点 15 加入队列
将节点 20 的右子节点 7 加入队列
当前层遍历完后，深度加1：
深度 depth： 2
队列 queue： [15, 7]
深度 depth： 2

第三层
当前层的节点数： levelSize = 2
遍历当前层的节点：
弹出节点 15，没有子节点
弹出节点 7，没有子节点
当前层遍历完后，深度加1：
深度 depth： 3
队列 queue： []
深度 depth： 3
结果
最终，队列为空，循环结束，返回深度 3。

总结
通过队列进行层次遍历，每遍历完一层，深度加1。这样可以有效地计算二叉树的最大深度。

递归方法

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

计算左子树的最大深度和右子树的最大深度，取两者中的较大值，然后加 1（当前节点的深度）

111. 二叉树的最小深度

介绍递归法

/**
 * 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 int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 如果左子树或右子树为空，则返回非空子树的最小深度
        if (root.left == null) {
            return 1 + minDepth(root.right);
        }
        if (root.right == null) {
            return 1 + minDepth(root.left);
        }
        // 如果左右子树都不为空，则返回左右子树的最小深度的较小值
        return 1 + Math.min(minDepth(root.left), minDepth(root.right));
    }
}

处理左子树或右子树为空的情况：

• 如果左子树为空，返回右子树的最小深度加1。
• 如果右子树为空，返回左子树的最小深度加1。

处理左右子树都不为空的情况：

• 如果左右子树都不为空，返回左右子树的最小深度的较小值，然后加1（当前节点的深度）。

标签：TreeNode,val,int,随想录,day14,二叉树,null,节点,left
From： https://blog.csdn.net/m0_73678713/article/details/143349105