当前位置: 首页 > article >正文

算法题目总结-二叉树

文章目录

    • 1.二叉树的最大深度
        • 1.答案
        • 2.思路
    • 2.相同的树
        • 1.答案
        • 2.思路
    • 3.翻转二叉树
        • 1.答案
        • 2.思路
    • 4.对称二叉树
        • 1.答案
        • 2.思路
    • 5.填充每个节点的下一个右侧节点指针 II
        • 1.答案
        • 2.思路
    • 6.二叉树展开为链表
        • 1.答案
        • 2.思路
    • 7.路径总和
        • 1.答案
        • 2.思路
    • 8.求根节点到叶节点数字之和
        • 1.答案
        • 2.思路
    • 9.二叉树的最近公共祖先
        • 1.答案
        • 2.思路
    • 10.二叉树的层序遍历
        • 1.答案
        • 2.思路
    • 11.二叉搜索树的最小绝对差
        • 1.答案
        • 2.思路
    • 12.验证二叉搜索树
        • 1.答案
        • 2.思路

1.二叉树的最大深度

1.答案
package com.sunxiansheng.arithmetic.day7;

import com.sunxiansheng.arithmetic.util.TreeNode;

/**
 * Description: 104. 二叉树的最大深度
 *
 * @Author sun
 * @Create 2025/1/9 10:16
 * @Version 1.0
 */
public class t104 {

    public int maxDepth(TreeNode root) {
        if (root == null) {
            // 如果当前节点为空,那么最大深度就是0
            return 0;
        } else {
            // 可以获取到左右子树的最大深度
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            // 取左右子树中深度最大的加一就是当前子树的最大深度
            return Math.max(left, right) + 1;
        }
    }
}
2.思路

取左右子树中深度最大的加一就是当前子树的最大深度

2.相同的树

1.答案
package com.sunxiansheng.arithmetic.day7;

import com.sunxiansheng.arithmetic.util.TreeNode;

/**
 * Description: 100. 相同的树
 *
 * @Author sun
 * @Create 2025/1/9 10:23
 * @Version 1.0
 */
public class t100 {

    public static boolean isSameTree(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        } else if (left == null || right == null) {
            return false;
        } else {
            // 先比较当前两个节点的值
            if (left.val != right.val) {
                return false;
            }
            // 当前两个节点的值如果相同,就比较两个子树是否是相同的树
            boolean leftTree = isSameTree(left.left, right.left);
            boolean rightTree = isSameTree(left.right, right.right);
            return leftTree && rightTree;
        }
    }
}
2.思路
  1. 参数,传递状态
  2. 终止条件:两个节点都为空返回true,两个节点一个为空就返回false
  3. 如果两个节点都不为空,则先比较两个节点的值,然后当左右子树都相同时就返回true

3.翻转二叉树

1.答案
package com.sunxiansheng.arithmetic.day8;

import com.sunxiansheng.arithmetic.util.TreeNode;

/**
 * Description: 226. 翻转二叉树
 *
 * @Author sun
 * @Create 2025/1/11 09:59
 * @Version 1.0
 */
public class t226 {

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            // 如果为空,直接返回即可,因为null就是翻转后的结果了
            return null;
        } else {
            TreeNode left = invertTree(root.left);
            TreeNode right = invertTree(root.right);
            // 翻转左右子树
            root.left = right;
            root.right = left;
            return root;
        }
    }
}
2.思路
  1. 参数传递状态
  2. 终止条件就是如果为null,就返回null,因为返回的就是翻转后的树了
  3. 然后在返回翻转后的左右子树之后,再将当前节点的左右子树翻转后返回即可

4.对称二叉树

1.答案
package com.sunxiansheng.arithmetic.day8;

import com.sunxiansheng.arithmetic.util.TreeNode;

/**
 * Description: 101. 对称二叉树
 *
 * @Author sun
 * @Create 2025/1/11 10:09
 * @Version 1.0
 */
public class t101 {

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 检查左右子树是否对称
        return check(root.left, root.right);
    }

    /**
     * 检查左右子树是否轴对称
     *
     * @param left
     * @param right
     * @return
     */
    private boolean check(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        } else if (left == null || right == null) {
            return false;
        } else {
            // 都不为空的情况,就先比较两个节点的值
            if (left.val != right.val) {
                return false;
            }
            // 到这里就是两个节点的值相同,则判断子树是否对称
            boolean leftTree = check(left.right, right.left);
            boolean rightTree = check(left.left, right.right);
            return leftTree && rightTree;
        }
    }
}
2.思路

就是相同的树,不过在传递状态的时候不同而已

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

1.答案
package com.sunxiansheng.arithmetic.day8;

import com.sunxiansheng.arithmetic.util.Node;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Description: 117. 填充每个节点的下一个右侧节点指针 II
 *
 * @Author sun
 * @Create 2025/1/11 10:19
 * @Version 1.0
 */
public class t117 {

    public Node connect(Node root) {
        // 层序遍历
        if (root == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            // 前一个节点的指针
            Node prev = null;
            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                // 只要前一个节点不是空,就指向当前节点
                if (prev != null) {
                    prev.next = node;
                }
                // 更新前一个节点的指针指向当前节点
                prev = node;
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        return root;
    }
}
2.思路

使用层序遍历,并记录前一个指针的值,只要前一个指针不为null,就让他的next指向当前节

6.二叉树展开为链表

1.答案
package com.sunxiansheng.arithmetic.day8;

import com.sunxiansheng.arithmetic.util.TreeNode;

/**
 * Description: 114. 二叉树展开为链表
 *
 * @Author sun
 * @Create 2025/1/11 10:30
 * @Version 1.0
 */
public class t114 {

    TreeNode prev = null;

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        } else {
            flatten(root.right);
            flatten(root.left);
            // 将当前节点的左子树置空
            root.left = null;
            // 当前节点的right指向prev
            root.right = prev;
            // 更新prev为当前节点
            prev = root;
        }
    }
}
2.思路

反前序遍历,先将当前子树的左节点置空,右节点指向prev,然后更新prev指向当前节点

7.路径总和

1.答案
package com.sunxiansheng.arithmetic.day8;

import com.sunxiansheng.arithmetic.util.TreeNode;

/**
 * Description: 112. 路径总和
 *
 * @Author sun
 * @Create 2025/1/11 10:44
 * @Version 1.0
 */
public class t112 {

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        boolean[] res = new boolean[1];
        backtrace(root, 0, res, targetSum);
        return res[0];
    }

    public static void backtrace(TreeNode root, int sum, boolean[] res, int targetSum) {
        // 累加结果
        sum += root.val;
        if (root.left == null && root.right == null) {
            if (sum == targetSum) {
                res[0] = true;
            }
            return;
        } else {
            if (root.left != null) {
                backtrace(root.left, sum, res, targetSum);
            }
            if (root.right != null) {
                backtrace(root.right, sum, res, targetSum);
            }
        }
    }
}
2.思路

对于每个节点,先计算当前节点的和,如果是叶子节点就直接与targetSum比较,如果不是叶子节点就传递状态

8.求根节点到叶节点数字之和

1.答案
package com.sunxiansheng.arithmetic.day8;

import com.sunxiansheng.arithmetic.util.TreeNode;

/**
 * Description: 129. 求根节点到叶节点数字之和
 *
 * @Author sun
 * @Create 2025/1/11 11:00
 * @Version 1.0
 */
public class t129 {

    public int sumNumbers(TreeNode root) {
        int[] res = new int[1];
        backtrace(root, new StringBuilder(), res);
        return res[0];
    }
    
    public static void backtrace(TreeNode root, StringBuilder sum, int[] res) {
        if (root.left == null && root.right == null) {
            // 计算和
            sum.append(root.val);
            // 累加和
            res[0] += Integer.valueOf(sum.toString());
            return;
        } else {
            // 计算和
            sum.append(root.val);
            if (root.left != null) {
                backtrace(root.left, sum, res);
                // 回溯
                sum.deleteCharAt(sum.length() - 1);
            }
            if (root.right != null) {
                backtrace(root.right, sum, res);
                // 回溯
                sum.deleteCharAt(sum.length() - 1);
            }
        }
    }
}
2.思路

这种路径问题,采用的遍历方式一定是root.left != null xxx root.right != null xxx 然后根节点使用的是root.left == null && root.right == null 这样就不会走到null节点了,然后再if和else都需要计算路径,回溯的话只有递归之后才回溯

9.二叉树的最近公共祖先

1.答案
package com.sunxiansheng.arithmetic.day9;

import com.sunxiansheng.arithmetic.util.TreeNode;

import java.util.Objects;

/**
 * Description: 236. 二叉树的最近公共祖先
 *
 * @Author sun
 * @Create 2025/1/13 09:33
 * @Version 1.0
 */
public class t236 {

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果目前的树为null或者是p或者q,那么公共祖先就是root
        if (root == null || root == p || root == q) {
            return root;
        } else {
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            // 如果都找不到公共祖先,就说明子树中没有p,q
            if (Objects.isNull(left) && Objects.isNull(right)) {
                return null;
            }
            // 如果有一个找到了公共祖先,那么公共祖先就是那个节点
            if (Objects.isNull(left) || Objects.isNull(right)) {
                return left == null ? right : left;
            }
            // 如果都找到了公共祖先,则当前节点就是公共祖先
            return root;
        }
    }
}
2.思路

如果目前的树为null或者是p或者q,那么公共祖先就是root,其他情况则从左右子树寻找公共祖先,如果都找不到,就说明左右子树没有p,q,则公共祖先为null,如果有一个找到了公共祖先,则公共祖先就是那个节点,如果都找到了公共祖先,则当前节点就是公共祖先

10.二叉树的层序遍历

1.答案
package com.sunxiansheng.arithmetic.day9;

import com.sunxiansheng.arithmetic.util.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Description: 二叉树的层序遍历
 *
 * @Author sun
 * @Create 2025/1/13 09:57
 * @Version 1.0
 */
public class t102 {

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        // 队列
        Queue<TreeNode> queue = new LinkedList<>();
        // 根节点入队
        queue.add(root);
        while (!queue.isEmpty()) {
            // 当前层的节点数
            int size = queue.size();
            // 存当前层节点
            List<Integer> list = new ArrayList<>();
            // 遍历当前层节点
            for (int i = 0; i < size; i++) {
                // 取出一个节点
                TreeNode node = queue.poll();
                // 放入列表
                list.add(node.val);
                // 左右节点入队
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            // 将当前层的节点放到列表中
            res.add(list);
        }
        return res;
    }
}
2.思路

标准的二叉树层序遍历

11.二叉搜索树的最小绝对差

1.答案
package com.sunxiansheng.arithmetic.day9;

import com.sunxiansheng.arithmetic.util.TreeNode;

/**
 * Description: 530. 二叉搜索树的最小绝对差
 *
 * @Author sun
 * @Create 2025/1/13 10:07
 * @Version 1.0
 */
public class t530 {

    public int getMinimumDifference(TreeNode root) {
        int[] res = new int[2];
        res[0] = Integer.MAX_VALUE;
        // 前一个节点的值初始化为-1
        res[1] = - 1;
        midderOrder(root, res);
        return res[0];
    }

    public void midderOrder(TreeNode root, int[] res) {
        if (root == null) {
            return;
        } else {
            midderOrder(root.left, res);
            // 如果前一个节点的值不为-1,才求差值
            if (res[1] != -1) {
                // 跟前一个节点求差值
                int diff = Math.abs(root.val - res[1]);
                // 然后跟当前的最小差值比较
                res[0] = Math.min(res[0], diff);
            }
            // 更新前一个节点
            res[1] = root.val;
            midderOrder(root.right, res);
        }
    }
}
2.思路

这里需要注意的点是如果前一个节点的值不为-1,才求差值,也就是要跳过第一个根

12.验证二叉搜索树

1.答案
package com.sunxiansheng.arithmetic.day9;

import com.sunxiansheng.arithmetic.util.TreeNode;

/**
 * Description: 98. 验证二叉搜索树
 *
 * @Author sun
 * @Create 2025/1/13 10:41
 * @Version 1.0
 */
public class t98 {

    public boolean isValidBST(TreeNode root) {
        return middleOrder(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean middleOrder(TreeNode root, long min, long max) {
        if (root == null) {
            return true;
        }
        if (root.val <= min || root.val >= max) {
            return false;
        }
        // 再判断左右子树的节点范围满不满足要求
        boolean left = middleOrder(root.left, min, root.val);
        boolean right = middleOrder(root.right, root.val, max);
        return left && right;
    }
}
2.思路

核心就是判断节点是否在从min到max的范围内


http://www.kler.cn/a/512409.html

相关文章:

  • C语言内存之旅:从静态到动态的跨越
  • mysql之基本常用的语法
  • 直驱式风电储能制氢仿真模型matlab/simulink
  • mysql查看binlog日志
  • Python文本处理:LDA主题聚类模型
  • JSON-stringify和parse
  • SuperMap iClient3D for WebGL选中抬升特效
  • oracle之行转列
  • 亲测有效!如何快速实现 PostgreSQL 数据迁移到 时序数据库TDengine
  • vue3+three.js加载glb模型
  • 基于SpringBoot + Mybatis Plus + SaToken + Thymeleaf + Layui的后台管理系统
  • Python基于Django的社区爱心养老管理系统设计与实现【附源码】
  • Cyber Security 101-Security Solutions-Firewall Fundamentals(防火墙基础)
  • Java Web开发高级——Spring Boot与Docker容器化部署
  • 电子电气架构 --- 车载通信诊断
  • 【开源免费】基于SpringBoot+Vue.JS密接者跟踪系统(JAVA毕业设计)
  • 大语言模型增强推荐系统:分类、趋势、应用与未来
  • c# PDF文件合并工具
  • python milvus及curl命令进行query请求
  • Java工程结构:服务器规约(JVM 碰到 OOM 场景时输出 dump 信息、设置tomcat的 JVM 的内存参数、了解服务平均耗时)
  • STM32更新程序OTA
  • 为AI聊天工具添加一个知识系统 之54 为事务处理 设计 基于DDD的一个 AI操作系统 来处理维度
  • npm配置electron专属的淘宝镜像进行安装
  • 2、ansible的playbook
  • MongoDB文档查询
  • PyTorch使用教程(11)-cuda的使用方法