🌈 01. 求二叉树结点个数

• 一棵二叉树的结点个数组成为：1 个根结点 + 左子树结点个数 + 右子树结点个数。

int TreeSize(TreeNode* root)
{//二叉树结点个数 = 左子树的结点个数 + 右子树结点个数 + 根结点return NULL == root ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

🌈 02. 求二叉树叶结点个数

• 二叉树的叶结点个数 = 左子树叶结点 + 右子树的叶结点。
• 只有左右孩子域皆为空的即为叶结点。

int TreeLeafSize(TreeNode* root)
{// 为空的结点肯定不是叶结点if (NULL == root){return 0;}// 左右孩子同时为空的结点位叶子结点if (NULL == root->left && NULL == root->right){return 1;}// 左右子树的叶子结点相加即为二叉树的总叶节点数量return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

🌈 03. 求二叉树的高度

• 如果当前树为空树，则返回 0
• 如果当前树不为空，当前树高度 = 最大子树高度 + 1 (根)

int TreeHeigh(TreeNode* root)
{	if (NULL == root)			// 当前结点为空的话即当前树为空树{return 0;}int left = (root->left);	// 记录左子树的高度int right = (root->right);	// 记录右子树的高度return Left > Right ? Left + 1 : Right + 1;
}

🌈 04. 求第 k 层结点个数

1. 如果树为空，则返回为 0；如果 k 为第一层，则返回 1。
2. 如果上述两种情况都不是，求以当前结点开始的第 k 层结点个数可以分化为求当前结点的左右子树的第 k - 1 层结点个数。
3. 重复递归执行第二步，直到分治到 k 为 1 或 0 为止。

int TreeLevelKSize(TreeNode* root, int k)
{assert(k > 0);		// 不存在第 0 层if (NULL == root)	// 空树结点个数为 0{return 0;	}if (1 == k)			// 每棵子树的第一层都是 1 个结点{return 1;	}return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}

🌈 05. 查找值为 x 的结点

• 当结点的值与 x 相等时，返回该节点，否则去其左右子树中寻找，若未找到，则返回空。

TreeNode* TreeFind(TreeNode* root, BTDataType x)
{// 当前结点为空则返回 NULLif (NULL == root)		{return NULL;}// 当前结点值和 x 相等时返回该结点if (root->data == x)	{return root;}// 去当前结点的左子树寻找，若不为空则说明找到了TreeNode* LeftRet =  TreeFind(root->left, x);if (LeftRet != NULL)	{return LeftRet;}// 去当前结点的右子树寻找，若不为空则说明找到了TreeNode* RightRet = TreeFind(root->right, x);if (RightRet != NULL)	{return RightRet;}// 当前子树的根结点以及其左右子树都未找到时返回 NULLreturn NULL;	
}

🌈 06. 判断是否是单值二叉树

单值二叉树

• 二叉树中每个结点的值都相同，即为单值二叉树。

解题思路

• 将一棵完整二叉树拆成若干份小二叉树，每个小二叉树包含 根结点、左孩子、右孩子 三部分。
• 让每棵小树的根结点分别与其左右孩子比较，有不相等的值则返回 false，如果相等则继续对左右子树执行该步骤，直到走到空为止。

bool isUnidataTree(TreeNode* root)
{if (NULL == root){return true;}// 左孩子不为空，但是左孩子的值与根节点不同if (root->left && root->data != root->left->data){return false;}// 右孩子不为空，但是右孩子的值与根节点不同if (root->right && root->data != root->right->data){return false;}// 按照上述方法查找大二叉树的每棵小树，只要有一个返回 false 就会一路返回 falsereturn isUnidataTree(root->left) && isUnidataTree(root->right);
}

🌈 07. 判断两棵树是否相同

1. 判断两棵树相同位置的结点是否同时为空。
2. 判断两棵树相同位置的非空结点的值是否相同。
3. 对这两棵树中的所有子树采用上述步骤。

bool isSameTree(TreeNode* p, TreeNode* q)
{// 两个相同位置结点都为空时自然相同if (NULL == p && NULL == q){return true;}// 如果两个相同位置的结点不是同时为空，两棵树肯定不相同if ((NULL == p && NULL != q) || (NULL != p && NULL == q)){return false;}// 判断相同位置结点的值是否相等if (p->data != q->data){return false;}// 重复上述步骤，如果有一个地方返回 false，则一直返回 falsereturn isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

🌈 08. 判断是否是对称二叉树

• 一个关于中心轴对称的二叉树称为对称二叉树。

实现思路

• 将二叉树拆分成 根节点、左子树、右子树 三部分，每棵子树都能拆成这三部分。
• 让左子树的根和右子树的根比较；让左子树的左子树和右子树的右子树比较；让左子树的右子树和右子树的左子树比较。

代码实现

bool _isSymmetric(TreeNode* left, TreeNode* right)
{// 两个子树的根结点都为空时对称if (NULL == left && NULL == right){return true;}// 相对称位置结点如果不是同时为空则结果肯定不对称if ((NULL == left && right != NULL) || (NULL == right && left != NULL)){return false;}// 相对位置都不为空且值不相等时不对称if (left->data != right->data){return false;}// 让左右子树的相对称位置的结点执行上述步骤return _isSymmetric(left->left, right->right) && _isSymmetric(left->right, right->left);
}bool isSymmetric(TreeNode* root)
{// 判断大二叉树的左右子树是否对称return _isSymmetric(root->left, root->right);
}

🌈 09. 另一棵树的子树

• 判断一棵小树是不是另一棵大树的子树。

实现思路

• 将大二叉树拆分成 根节点、左子树、右子树 三部分。大树的所有子树都可拆成这三部分。
• 在大树的这三部分去找与小树相同的子树。

代码实现

// 判断两棵树是否相同
bool isSameTree(TreeNode* p, TreeNode* q)
{//两个结点都为空时自然相同if (NULL == p && NULL == q){return true;}//如果两个相同位置的结点不是同时为空，两棵树肯定不相同if ((NULL == p && NULL != q) || (NULL != p && NULL == q)){return false;}//判断相同位置结点的值是否相等if (p->data != q->data){return false;}//重复上述步骤，如果有一个地方返回 false，则一直返回 falsereturn isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}bool isSubtree(TreeNode* root, TreeNode* subRoot)
{if (NULL == root){return false;}// 将大二叉树拆成根节点、左子树、右子树 三部分，去和小二叉树比较return isSameTree(root, subRoot) || isSubtree(root->left, subRoot) ||isSubtree(root->right, subRoot);
}

🌈 10. 判断是否为完全二叉树

• 此功能实现要借助数据结构的队列。

实现思路

• 因为完全二叉树中的所有结点都是连续的。
• 将二叉树中所有的结点 (包括空结点) 按照层序的方式依次入队列。
• 然后将队列中的结点依次出队，如果出到了 NULL 则停止出队。
• 此时再查看队列中是否还有非空结点 (表示不连续)，如果有，则该二叉树不是完全二叉树。

举个例子

代码实现

bool BinaryTreeComplete(TreeNode* root)
{Queue q;						// 创建队列QueueInit(&q);					// 队列初始化if (root)						// 根结点非空时入队列{QueuePush(&q, root);}while (!QueueEmpty(&q))			// 队列非空则二叉树没有遍历完{TreeNode* front = QueueFront(&q);QueuePop(&q);				// 队头出队列if (NULL == front)			// 出到 NULL 时结束出队列{break;}QueuePush(&q, front->left);	// 将包含 NULL 在内的当前出队结点的 左孩子 入队QueuePush(&q, front->right);// 将包含 NULL 在内的当前出队结点的 右孩子 入队}while (!QueueEmpty(&q))			// 队列非空时判断是否还有非 NULL 元素{TreeNode* front = QueueFront(&q);QueuePop(&q);				// 不停出队列用于检查是否有空结点if (front)					// 出现不是 NULL 说明不是完全二叉树{QueueDestroy(&q);		// 销毁队列return false;			// 非完全二叉树}}QueueDestroy(&q);				// 销毁队列return true;					// 是完全二叉树
}