数据结构之二叉树（4）

（注：本文所示代码均为C++）

一.二叉树选择题

根据二叉树的性质，完成以下选择题:
 
（1）第一组
 
某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A 不存在这样的二叉树
B 200
C 198
D 199
 
在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/2
 
一棵完全二叉树的结点数位为 531 个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 12
 
一个具有 767 个结点的完全二叉树，其叶子结点个数为（）
A 383
B 384
C 385
D 386
 
（2）链式二叉树遍历选择题
 
某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（ ）
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA
 
二叉树的先序遍历和中序遍历如下: 先序遍历: EFHIGJK;中序遍历: HFI EJKG, 则二叉树根结点为（）
A E
B F
C G
D H
 
设一课二叉树的中序遍历序列: badce，后序遍历序列: bdeca，则二叉树前序遍历序列为____。
A adbce
B decab
C debac
D abcde
 
某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列为
A FEDCBA
B CBAFED根据二叉树的性质，完成以下选择题:

 

选择题答案

 二.二叉树编程题

1.单值二叉树

 LeetCode 965题聚焦“单值二叉树”。题目要求判断给定二叉树的每个节点值是否相同，若是则为单值二叉树，需返回 true ，否则返回 false  。示例展示了一棵节点值均为1的二叉树。

 

右侧代码中， Solution 类的 isUnivalTree 函数展开判断逻辑。首先，若根节点为空，按照定义它是单值二叉树（空树特殊情况），直接返回 true  。接着，检查根节点的左子节点（若存在），一旦其值与根节点值不同，说明树不是单值的，返回 false  ；对右子节点也执行相同检查。最后，通过递归方式，继续检查左子树和右子树是否为单值二叉树，只有左右子树都满足单值条件，整棵树才是单值二叉树，此时返回 true  ，全面且严谨地实现了题目要求。

 

2.相同的树

 LeetCode 100题“相同的树”，旨在判断给定的两棵二叉树在结构和节点值上是否完全一致。解题的核心在于递归地比较两棵树的节点。

 代码中， isSameTree 函数先处理边界情况：若两棵树的当前节点都为空，说明这部分结构相同，返回 true ；若其中一棵为空而另一棵不为空，结构不一致，返回 false ；若节点值不同，也返回 false 。然后，通过递归调用自身分别检查两棵树的左子树和右子树是否相同，只有当左右子树都相同时，两棵树才是完全相同的，以此实现对两棵二叉树是否相同的准确判断。

 

3.另一棵子树

 LeetCode 572题“另一棵树的子树”，任务是判断二叉树 root 中是否存在与 subRoot 结构和节点值都相同的子树。解题关键在于比较两棵树的结构和节点值。

 

代码中， isSameTree 函数用于判断两棵树是否完全相同。先处理边界情况，若两棵树都为空，返回 true ；若一棵为空另一棵不为空，返回 false ；若根节点值不同，也返回 false ；然后递归检查左右子树。 isSubtree 函数则以 root 树的每个节点为起点，调用 isSameTree 函数判断是否存在与 subRoot 相同的子树，通过递归遍历 root 树的左右子树来完成整体判断，逻辑清晰地解决了子树判断问题。