# 二叉树顶上战争实战——手撕数据结构

🎉🎉非科班转码社区诚邀您入驻🎉🎉

3
/
9 20
/
15 7

## 实现🤔

``````int maxDepth(struct TreeNode* root){
if(root==NULL)
{
return 0;
}
int m = maxDepth(root->left);//左子树遍历
int n = maxDepth(root->right);//右子树遍历
return m>n?m+1:n+1;//返回较大的一方（不要忘了加上根节点）
}
``````

# 2.单值二叉树🤔

``````bool dfs(struct TreeNode* root,int k)
{if(root == NULL)
{
return true;
}//排除空树
if(dfs(root->left,k)==false)
{
return false;//左子树节点不匹配
}
if(dfs(root->right,k)==false)
{
return false;//右子树节点不匹配
}
if(root->val!=k)
{
return false;//根节点节点不匹配
}
return true;
}
bool isUnivalTree(struct TreeNode* root){
return dfs(root,root->val);//递归调用遍历Tree
}
``````

## Tree节点数🤔

``````int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int m = BinaryTreeSize(root->left);
int n = BinaryTreeSize(root->right);
return m + n + 1;
}
``````

## 叶子节点个数🤔

``````int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
int m = BinaryTreeLeafSize(root->left);
int n = BinaryTreeLeafSize(root->right);
return m + n;
}
``````

## 第K层节点数🤔

``````int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;//找到目标层所满足的K值
}
int m = BinaryTreeLevelKSize(root->left, k - 1);
int n = BinaryTreeLevelKSize(root->right, k - 1);
return m + n;
}
``````

# 三大遍历👏

## 前序遍历🤔

``````void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
if (root)
{
putchar(root->data);
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
}
}
``````

## 中序遍历🤔

``````void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
BinaryTreeInOrder(root->left);
putchar(root->data);
BinaryTreeInOrder(root->right);
}
``````

## 后序遍历🤔

``````void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
putchar(root->data);
}
``````

THE END