1、求二叉樹結點的個數

核心思想：
結點個數等于左子樹+右子樹+1

int BinaryTreeSize(BTNode* root)
{
    return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

2、求葉子節點的個數

核心思想：
結點為空 return 0
結點為葉子 return 1
非空且不是葉子 return 左子樹葉子節點數+右子樹葉子節點數

int TreeLeafSize(BTNode* root)
{
    if (root == NULL)
        return 0;
   
    if (root->left == NULL && root->right == NULL)
        return 1;

    return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

3、求樹的深度

核心思想：
return 子樹較大者+1

int maxDepth(BTNode* root)
{
    if (root == NULL)
        return 0;

    return fmax(maxDepth(root->left), maxDepth(root->left)) + 1;
}

4、求第K層的結點數

核心思想：
求第K層，轉換成求左右子樹的第K-1層

int TreeKLevelSize(BTNode* root,int k)
{
    assert(k >= 1);

    if (root == NULL)
        return 0;

    if (k == 1)
        return 1;

    return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1);
}

5、查找樹里面值為x的節點

核心思想：
分別去左右子樹找，先看左子樹，左子樹沒有找到去右子樹找，找到了回傳

BTNode* TreeFind(BTNode* root, int x)
{
    if (root == NULL)
        return NULL;

    if (root->date == x)
        return root;

    BTNode* leftret = TreeFind(root->left,x);
    if (leftret)
        return leftret;
    BTNode* rightret = TreeFind(root->right, x);
    if (rightret)
        return rightret;

    return NULL;
}

6、判斷是否是單值二叉樹，每個結點值相等

OJ鏈接

bool isUnivalTree(BTNode* root)
{
    if (root == NULL)
        return true;

    if (root->left && root->left->date != root->date)
        return false;
    if (root->right && root->right->date != root->date)
        return false;
    
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

7、前序遍歷二叉樹，將值放到陣列

OJ鏈接

int TreeSize(struct TreeNode*root)
{
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}

void _preorderTraversal(struct TreeNode*root,int*a,int*pi)
{
    if(root==NULL)
    return ;
    
    a[(*pi)++]=root->val;

    _preorderTraversal(root->left,a,pi);
    _preorderTraversal(root->right,a,pi);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int size=TreeSize(root);
    int*a=(int*)malloc(sizeof(int)*size);
    int i=0;
    _preorderTraversal(root,a,&i);
    *returnSize=size;
    return a;
}

8、翻轉二叉樹

BTNode* invertTree(BTNode* root)
{
    if (root == NULL)
        return NULL;

    BTNode* tmp = invertTree(root->left);
    root->left = invertTree(root->right);
    root->right = tmp;
    return root;
}

9、判斷是否是相同的二叉樹

OJ鏈接

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p==NULL&&q==NULL)
    return true;

    if(p==NULL||q==NULL)
    return false;

    if(p->val!=q->val)
    return false;

    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

10、判斷是否是對稱二叉樹

OJ鏈接

bool _isisSymmetric(struct TreeNode*root1,struct TreeNode*root2)
{
    if(root1==NULL&&root2==NULL)
    return true;

    if(root1==NULL||root2==NULL)
    return false;

    if(root1->val!=root2->val)
    return false;

    return _isisSymmetric(root1->left,root2->right)
    &&_isisSymmetric(root1->right,root2->left);
}

bool isSymmetric(struct TreeNode* root){
    if(root==NULL)
    return true;

    return _isisSymmetric(root->left,root->right);
}

11、判斷是否是另一棵樹的子樹

OJ鏈接
核心思想：
用root的每一個子樹都和subRoot比較一下

bool isSameTree(struct TreeNode*p,struct TreeNode*q)
{
    if(p==NULL&&q==NULL)
    return true;

    if(p==NULL||q==NULL)
    return false;

    if(p->val!=q->val)
    return false;

    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root==NULL)
    return false;

    if(isSameTree(root,subRoot))
    return true;

    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

12、判斷是否是完全二叉樹

核心思想：
如果是完全二叉樹，層序遍歷，非空結點是連續的，
而不是完全二叉樹的非空結點不連續，

bool BinaryTreeComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front == NULL)
            break;

        else
        {
            QueuePush(&q, front->left);
            QueuePush(&q, front->right);
        }
    }

    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front)
        {
            QueueDestroy(&q);
            return false;
        }
    }
    QueueDestroy(&q);
    return true;
}

13、前序遍歷一個輸入的字串，用中序遍歷列印

OJ鏈接

#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode
{
    struct TreeNode*left;
    struct TreeNode*right;
    char data;
}TreeNode;

TreeNode*CreateTree(char*str,int*pi)
{
    if(str[*pi]=='#')
    {
        (*pi)++;
        return NULL;
    }
    TreeNode*root=(TreeNode*)malloc(sizeof(TreeNode));
    root->data=str[(*pi)++];
    root->left=CreateTree(str,pi);
    root->right=CreateTree(str,pi);
    return root;
}

void Inorder(TreeNode*root)
{
    if(root==NULL)
        return ;
    
    Inorder(root->left);
    printf("%c ",root->data);
    Inorder(root->right);
}

int main()
{
    char str[100];
    while(scanf("%s ",str)!=EOF)
    {
        int i=0;
        TreeNode*root=CreateTree(str,&i);
        Inorder(root);
    }
    return 0;
}

感謝閱讀，我們下期再見
如有錯 歡迎提出一起交流