剑指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的位置序号一一对应,则为完全二叉树。可见,满二叉树必为完全二叉树,而完全二叉树不一定是满二叉树。

题目

二叉树的镜像

典型题例:

输入一个二叉树,将它变换为它的镜像。

示例 :

输入树:
      8
     / \
    6  10
   / \ / \
  5  7 9 11
 [8,6,10,5,7,9,11,null,null,null,null,null,null,null,null] 
输出树:
      8
     / \
    10  6
   / \ / \
  11 9 7  5
 [8,10,6,11,9,7,5,null,null,null,null,null,null,null,null]

思路

核心

我们可以发现镜像后的树就是将原树的所有节点的左右儿子互换!

所以我们递归遍历原树的所有节点,将每个节点的左右儿子互换即可。

代码:

/**
 * 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:
    void mirror(TreeNode* root) {
        //判断参数
        if (!root)  return;
        swap(root->left, root->right);  //交换左右子树
        mirror(root->left);             //递归遍历
        mirror(root->right);
    }
};

对称的二叉树

典型题例:

请实现一个函数,用来判断一棵二叉树是不是对称的。

如果一棵二叉树和它的镜像一样,那么它是对称的。

示例 :

如下图所示二叉树[1,2,2,3,4,4,3,null,null,null,null,null,null,null,null]为对称二叉树:
    1
   / \
  2   2
 / \ / \
3  4 4  3
如下图所示二叉树[1,2,2,null,4,4,3,null,null,null,null,null,null]不是对称二叉树:
    1
   / \
  2   2
   \ / \
   4 4  3

思路

递归判断两个子树是否互为镜像。

两个子树互为镜像当且仅当:

  1. 两个子树的根节点值相等;
  2. 第一棵子树的左子树和第二棵子树的右子树互为镜像,且第一棵子树的右子树和第二棵子树的左子树互为镜像;

代码:

/**
 * 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:
    bool isSymmetric(TreeNode* root) {
        if (!root)  return true;       //判断参数
        return dfs (root->left, root->right);   
    }
    bool dfs(TreeNode* p, TreeNode* q){
        if (!p || !q)   return !p && !q; //当p,q其中一个为空时,只有当p,q都为空返回true
        if (p->val != q->val)   return false;   //值不相等为false
        return dfs (p->left, q->right) && dfs (p->right, q->left);  //递归遍历左右孩子
    }
};

充电站

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

相关文章
|
文件存储
PowerShell系列(十):PowerShell CmdletPowerShell Cmdlet 参数详解
【2月更文挑战第5篇】强制类型参数使用比较频繁,基本上涉及新建、更新、配置等命令都需要针对特定的对应进行操作,所有需要强制输入一个参数来确认操作的对象是谁。
PowerShell系列(十):PowerShell CmdletPowerShell Cmdlet 参数详解
|
12月前
|
域名解析 网络协议
阿里云如何找回域名,进行添加或删除?
阿里云如何找回域名,进行添加或删除?
|
机器学习/深度学习 自然语言处理 搜索推荐
一文掌握jieba分词器的常见用法,附带案例
该文章全面介绍了jieba分词器的使用方法,包括安装步骤、不同分词模式的使用,以及如何通过实例代码进行文本分词处理。
1349 0
|
缓存 自然语言处理 JavaScript
Vue 3 渲染机制解密:从模板到页面的魔法
Vue 3 渲染机制解密:从模板到页面的魔法
577 0
|
消息中间件 Kafka Linux
kafka3.0创建topic出现zookeeper is not a recognized option
kafka3.0创建topic出现zookeeper is not a recognized option
466 0
【python】提取多个excel的工作簿,生成新的excel
【python】提取多个excel的工作簿,生成新的excel
|
索引 Python
Python数据结构讲解集合
Python数据结构讲解集合
78 0
|
Docker 容器
百度搜索:蓝易云【Docker下如何实现Docker Compose?】
现在,你已经成功使用Docker Compose在Docker中配置和管理多个容器服务。你可以在 `docker-compose.yml`文件中根据需要添加更多的服务和配置。
130 0
|
机器学习/深度学习 人工智能 资源调度
论文解读系列 | 01:【NER】W2NER (AAAI 2022)
2022 AAAI论文《Unified Named Entity Recognition as Word-Word Relation Classification》介绍了一个统一NER的SOTA模型W2NER,该模型在14个包含**扁平实体、重叠实体和非连续**实体的数据集(8个英文 + 6个中文)上,均取得了**SOTA**的结果(F1指标)。W2NER将NER问题视为词词关系分类,为此引入两种词词关系:NNW(Next-Neighboring-Word)和 THW-\*(Tail-Head-Word-\*)。具体而言,构造一个 2D 的词词关系网格。
|
运维 监控 网络协议
DeepFlow 电信运营商5G核心网可靠性监控运维最佳实践
随着CT与IT技术的融合以及5GC NFV化的发展,逐渐暴露出IT技术对通信网络可靠性的影响。云计算技术可以为通信网络带来硬件通用化、弹性化、资源池化,业务迭代加速等好处,但原有专用设备的可靠性、易维护性在新的云架构中面临巨大挑战。DeepFlow基于云原生的软探针流量采集技术、智能流量分析技术,实现对5GC云资源池硬件层网络接口、虚拟层网络接口、VNF层网络接口的全栈流量采集和分析,搭建5GC网络智能监控分析平台。
1187 0
DeepFlow 电信运营商5G核心网可靠性监控运维最佳实践