代码随想录 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、鼠标中键点击书签即打开新的标签页,在新的标签页中显示指定的网页。
58931 0
|
运维 Kubernetes 监控
Loki+Promtail+Grafana监控K8s日志
综上,Loki+Promtail+Grafana 监控组合对于在 K8s 环境中优化日志管理至关重要,它不仅提供了强大且易于扩展的日志收集与汇总工具,还有可视化这些日志的能力。通过有效地使用这套工具,可以显著地提高对应用的运维监控能力和故障诊断效率。
1477 0
|
网络安全 Windows
PentestGPT-V0(1),网络安全面试题2024笔试
PentestGPT-V0(1),网络安全面试题2024笔试
|
15天前
|
存储 弹性计算 人工智能
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
2025年9月24日,阿里云弹性计算团队多位产品、技术专家及服务器团队技术专家共同在【2025云栖大会】现场带来了《通用计算产品发布与行业实践》的专场论坛,本论坛聚焦弹性计算多款通用算力产品发布。同时,ECS云服务器安全能力、资源售卖模式、计算AI助手等用户体验关键环节也宣布升级,让用云更简单、更智能。海尔三翼鸟云服务负责人刘建锋先生作为特邀嘉宾,莅临现场分享了关于阿里云ECS g9i推动AIoT平台的场景落地实践。
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
|
6天前
|
云安全 人工智能 安全
Dify平台集成阿里云AI安全护栏,构建AI Runtime安全防线
阿里云 AI 安全护栏加入Dify平台,打造可信赖的 AI
|
9天前
|
人工智能 运维 Java
Spring AI Alibaba Admin 开源!以数据为中心的 Agent 开发平台
Spring AI Alibaba Admin 正式发布!一站式实现 Prompt 管理、动态热更新、评测集构建、自动化评估与全链路可观测,助力企业高效构建可信赖的 AI Agent 应用。开源共建,现已上线!
877 32