代码随想录 Day14 - 二叉树(一)

简介: 代码随想录 Day14 - 二叉树(一)

相关概念


满二叉树


一棵深度为 k 且有 个结点的二叉树称为满二叉树。

节点数 = 2^k - 1


完全二叉树


除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树。

每一层从左到右都不缺失节点,完全二叉树一定是满二叉树。


二叉搜索树


二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值。


平衡二叉搜索树


平衡二叉搜索树(英语:Balanced Binary Tree)是一种结构平衡的二叉搜索树,即叶节点高度差的绝对值不超过 1,并且左右两个子树都是一棵平衡二叉树。


作业题


递归法遍历二叉树


144. 二叉树的前序遍历

/**
 * 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<>();
        dfs(root, result);
        return result;
    }
    private void dfs(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
         result.add(node.val);
        dfs(node.left, result);
        dfs(node.right, result);
    }
}


94. 二叉树的中序遍历

/**
 * 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> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, result);
        return result;
    }
    private void dfs(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        dfs(node.left, result);
        result.add(node.val);
        dfs(node.right, result);
    }
}


145. 二叉树的后序遍历

/**
 * 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> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, result);
        return result;
    }
    private void dfs(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        dfs(node.left, result);
        dfs(node.right, result);
        result.add(node.val);
    }
}


迭代法遍历二叉树


后续再补充。。。

144. 二叉树的前序遍历


94. 二叉树的中序遍历


145. 二叉树的后序遍历


目录
相关文章
|
8月前
|
数据采集 算法 Java
如何在Java爬虫中设置动态延迟以避免API限制
如何在Java爬虫中设置动态延迟以避免API限制
|
Web App开发
如何设置谷歌浏览器在新窗口中打开链接?如何设置谷歌浏览器在新标签页中打开链接?
一、快捷键方式:  1、左键单击 ==》 在当前窗口中打开目标网页。  2、Shift + 左键单击 ==》 在新窗口中打开目标网页。  3、Ctrl + 左键单击 ==》 在新标签页中打开目标网页。  4、鼠标中键点击书签即打开新的标签页,在新的标签页中显示指定的网页。
58570 0
|
运维 Kubernetes 监控
Loki+Promtail+Grafana监控K8s日志
综上,Loki+Promtail+Grafana 监控组合对于在 K8s 环境中优化日志管理至关重要,它不仅提供了强大且易于扩展的日志收集与汇总工具,还有可视化这些日志的能力。通过有效地使用这套工具,可以显著地提高对应用的运维监控能力和故障诊断效率。
1385 0
|
网络安全 Windows
PentestGPT-V0(1),网络安全面试题2024笔试
PentestGPT-V0(1),网络安全面试题2024笔试
|
4天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
15天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1309 5
|
1天前
|
监控 JavaScript Java
基于大模型技术的反欺诈知识问答系统
随着互联网与金融科技发展,网络欺诈频发,构建高效反欺诈平台成为迫切需求。本文基于Java、Vue.js、Spring Boot与MySQL技术,设计实现集欺诈识别、宣传教育、用户互动于一体的反欺诈系统,提升公众防范意识,助力企业合规与用户权益保护。