剑指offer常见题 - 二叉树问题(一)

简介: 剑指offer常见题 - 二叉树问题(一)

二叉树相关算法

二叉树相关性质:

性质一:在二叉树的第i层上至多有2^(i-1)个结点(i>=1)

性质二:深度为k的二叉树至多有2^(k-1)个结点(k>=1)

性质三:对任意一颗二叉树T,若终端结点数为n0 ,而其度数为2的结点数为n2,则n0=n2+1

性质四:具有n个结点的完全二叉树的深度为 ⌊log n⌋+1(以2为底)

满二叉树:深度为k,且有2^(k-1)个结点的二叉树。 在满二叉树中,每层结点都是满的,即每层节点都具有最大结点数。

完全二叉树:深度为k,结点数为n的二叉树,如果其结点1n的位置序号分别于满二叉树的节点1n的位置序号一一对应,则为完全二叉树。可见,满二叉树必为完全二叉树,而完全二叉树不一定是满二叉树。

题目

重建二叉树

典型题例:

输入一棵二叉树前序遍历和中序遍历的结果,请重建该二叉树。

示例 :

给定:
前序遍历是:[3, 9, 20, 15, 7]
中序遍历是:[9, 3, 15, 20, 7]
返回:[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示:
    3
   / \
  9  20
    /  \
   15   7

思路

核心:

代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    //哈希map
    unordered_map<int, int> pos;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
       int n = preorder.size(); //for循环中<=时,n=preorder.size() - 1
       //遍历中序序列
       for (int i = 0; i < n; i ++) 
            pos[inorder[i]] = i;    //在哈希表中记录每个值在中序遍历中的位置
        return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
    }
    TreeNode *dfs(vector<int> &pre, vector<int> &in, int pl, int pr, int il, int ir){
            if(pl > pr)   return nullptr;
            //pl为root,在中序遍历中的位置-最左端的值为左子树长度
            int k = pos[pre[pl]] - il;  
            TreeNode *root = new TreeNode(pre[pl]); //定义根结点
            root->left = dfs(pre, in, pl + 1, pl + k, il, il + k - 1);  //递归遍历左子树
            root->right = dfs(pre, in, pl + k +1, pr, il + k + 1, ir);  //递归遍历右子树
            return root;
    }
};

二叉树的下一个节点

典型题例:

给定一棵二叉树的其中一个节点,请找出中序遍历序列的下一个节点。

注意:

  • 如果给定的节点是中序遍历序列的最后一个,则返回空节点;
  • 二叉树一定不为空,且给定的节点一定不是空节点;

示例 :

输入:
假定二叉树是:[2, 1, 3, null, null, null, null], 给出的是值等于2的节点。
则应返回值等于3的节点。
解释:该二叉树的结构如下,2的后继节点是3。
  2
 / \
1   3

思路

代码:

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
        if(p->right){       //存在右子树,找到右子树最左侧的节点就是当前节点的后继
            p = p->right;
            while(p->left)  p = p->left;
            return p;
        }
        //无右子树,沿father域找到第一个实其father左儿子的节点,该节点的father节点是当前节点的后继
        while(p->father && p == p->father->right) p = p->father;
        return p->father;
    }
};

充电站

推荐一个零声学院免费公开课程,个人觉得老师讲得不错,分享给大家:Linux,Nginx,ZeroMQ,MySQL,Redis,fastdfs,MongoDB,ZK,流媒体,CDN,P2P,K8S,Docker,TCP/IP,协程,DPDK等技术内容,立即学习

相关文章
|
6天前
|
Linux Go 开发工具
手机上跑 DeepSeek 智能体:开源安卓客户端 DSH Go 安装与使用指南
DSH Go 是一款开源安卓客户端,将 DeepSeek Harness 智能体引擎装进手机:免 Root、免 Termux,一键安装即用;支持本机运行(内置 Ubuntu+Node.js)或远程接管电脑会话;具备插话打断、过程折叠、屏幕操控、端到端加密分享等特色功能,真正实现智能体“口袋化”。
7059 17
|
6天前
|
弹性计算 人工智能 API
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
建议收藏本教程,2026 全年各版本更新随时回来查阅。如果你在搭建过程中遇到任何问题,欢迎结合 阿里云工单系统 提交技术支持请求,或在 阿里云开发者社区 搜索 Codex 相关话题交流。 祝你编码愉快,效率翻倍!
2334 10
|
8天前
|
人工智能 前端开发 API
阿里云Qwen4-Max 大模型详解:定位、特征、能力、适用场景与相对Qwen3-Max差异解析
2026年11月11日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问AI平台Token Plan并接入千问办公、Qoder等入口。该版本聚焦知识理解、世界感知、编程与Agentic四项升级,主打复杂编程、专业办公、前端设计与专业软件操作等真实任务。预览期为11月11日10:00至11月25日24:00,仅支持Token Plan调用,到期后模型标识下线;限时2折、新用户再享5折,最低1折可体验。
|
8天前
|
JSON 前端开发 API
阿里云最新Qwen4-Max大模型介绍:模型定位、特征、能力、适用场景解析
2026 年 11 月 11 日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问 AI 平台 Token Plan,并同步接入千问办公、Qoder 等入口。该版本聚焦知识理解、世界感知、编程与 Agentic 四项升级,主打复杂编程、专业办公、前端设计与专业软件操作。预览期至 11 月 25 日 24:00,到期后模型标识下线;限时 2 折、新用户再享 5 折,最低 1 折可体验。
|
4天前
|
传感器 安全 区块链
Windows 电脑运行安卓应用教程:开源工具 ApkStart 双击 APK 即装、独立窗口运行
ApkStart 是一款开源Windows工具,让安卓APP像原生软件一样运行:双击APK即安装、生成真实图标、独立窗口启动、开始菜单可搜索。无需传统模拟器,内置QEMU运行时,支持数据互通、ARM兼容与命令行操作。(239字)
|
21天前
|
Linux 开发工具 iOS开发
Codex保姆级教程(下载+安装+登录+使用,含所有版本,2026最新)
Codex是OpenAI推出的开源AI编程智能体,本地运行,可理解整个代码库,支持自然语言指令改代码、执行命令、跑测试、修Bug,兼容Win/macOS/Linux。(239字)
10222 59
|
4天前
|
人工智能 弹性计算 开发工具
零成本玩各大模型!DeepSeek Harness dsh-our-free-model 插件,13 个厂商模型直接用
总结一下:装这个插件,你不用注册、不用绑卡、不用填一个 Key,就能在 DeepSeek Harness 里用上 DeepSeek V4.1 Flash、Kimi K3 这一批前沿模型,而且是白嫖的、还不限量。三步搞定:下载插件,复制包含 `package.json` 的插件目录路径,在「添加插件」里粘贴路径安装并重启。无论是在阿里云 ECS 上通过命令行部署的 Web 版,还是本地的 Electron 桌面端,都能顺利跑通,快速搭建一套零成本的免费模型使用环境。
1058 1
|
7天前
|
Linux API iOS开发
【DSH】DeepSeek Harness新手保姆教程(下载+安装+配置+使用,2026最新实测)
DeepSeek Harness(dsh)是DeepSeek AI开源的智能体框架,秉持“一切皆插件”理念,支持读文件、改代码、跑命令、处理表格、联网搜索等操作。免费开源,兼容Windows/macOS/Linux,提供桌面端与网页端,可灵活安装插件扩展能力。
|
16天前
|
Linux 开发工具 iOS开发
2026最新codex下载安装保姆级使用教程(下载+安装+登录+使用,含所有历史版本)
本文详解OpenAI Codex国内快速上手指南:提供Win/macOS/Linux全平台免安装包、npm/Homebrew等多方式安装、账号/API Key双登录、简体中文切换,覆盖下载、安装、汉化、使用及高频避坑(如微软商店失败、npm超时等),10分钟即可跑通。
3499 9