如有不懂的地方，可查閱往期相關文章！
? ? ? ? ? ? ? ? ? ? 個人主頁：小八哥向前沖~
? ? ? ? ? ? ? ? ? ??所屬專欄：數據結構【c語言】
目錄
單值二叉樹
對稱二叉樹
計算二叉樹的深度
二叉樹的前序遍歷
相同二叉樹
另一棵樹的子樹
二叉樹的構建和遍歷
翻轉二叉樹
判斷平衡二叉樹
單值二叉樹
題目：
詳情：單值二叉樹_LeetCode
思路：
運用遞歸，每次遞歸將根，左孩子，右孩子進行比較！
而最后一次就是左子樹，右子樹和根的比較！
代碼：
bool isUnivalTree(struct TreeNode* root) {//遞歸//每次遞歸看成根，左孩子，右孩子比較//最后一次遞歸是左子樹和右子樹和根比較if(root==NULL)return true;//左子孩子存在就開始比較if(root->left&&root->val!=root->left->val)return false;//右孩子存在就開始比較if(root->right&&root->val!=root->right->val)return false;return isUnivalTree(root->left)&&isUnivalTree(root->right);
}對稱二叉樹
題目：
詳情：判斷對稱二叉樹_LeetCode
思路：
運用遞歸，將左子樹和右子樹進行比較！
所以需要分裝一個函數比較左子樹和右子樹。
這個函數里面的左子樹的左孩子要和右子樹的右孩子比較，左子樹的右孩子要和右子樹的左孩子比較！
圖：
代碼：
bool _checkSymmetricTree(struct TreeNode*q,struct TreeNode*p)
{//遞歸//最后一次遞歸是q的左子樹和p的右子樹判斷，q的右子樹和p的左子樹判斷//每次遞歸看作q的根和p的根判斷，q的孩子和p的孩子判斷是否相等if(q==NULL&&p==NULL)return true;//如果倆根只有一個為空就是假if(q==NULL||p==NULL)return false;if(q->val!=p->val)return false;return _checkSymmetricTree(q->left,p->right)&&_checkSymmetricTree(q->right,p->left);
}
bool checkSymmetricTree(struct TreeNode* root) {//遞歸//最后一次遞歸是左子樹和右子樹是否相等if(root==NULL)return true;return _checkSymmetricTree(root->left,root->right);
}計算二叉樹的深度
題目：
詳情：計算二叉樹深度_LeetCode
思路：
我們不難看出：樹的高度==高的子樹的高度+1。
代碼：
int calculateDepth(struct TreeNode* root) {//左子樹和右子樹比較，大的子樹加+1就是高度if(root==NULL)return 0;int leftheight=calculateDepth(root->left);int rightheight=calculateDepth(root->right);return leftheight>rightheight?leftheight+1:rightheight+1;
}二叉樹的前序遍歷
題目：
前序遍歷二叉樹，將值存到數組中。
詳情：二叉樹的前序遍歷_LeetCode
思路：
為了開辟的數組不大不小，我們計算樹節點總數，然后進行前序遍歷一個一個將樹節點數值寫入數組中。
以此則中序遍歷和后序遍歷也是如此！
代碼：
int TreeSize(struct TreeNode*root)
{//左子樹節點+右子樹節點+1return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
void preorder(struct TreeNode*root,int*a,int*i)
{if(root==NULL)return;a[(*i)++]=root->val;preorder(root->left,a,i);preorder(root->right,a,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {//為了開辟的數組不大不小，我們先計算樹的節點總數*returnSize=TreeSize(root);int*a=(int*)malloc(sizeof(int)*(*returnSize));int i=0;preorder(root,a,&i);return a;
}相同二叉樹
題目：
詳情：相同的樹_LeetCode
思路：
運用遞歸，分別將倆棵樹的根和根比較，左子樹和左子樹比較，右子樹和右子樹比較！
圖：
代碼：
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//p的左子樹和q的左子樹比較，p的右子樹和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);
}另一棵樹的子樹
題目：
詳情：另一顆子樹_LeetCode
思路：
將樹的所有子樹和另一棵樹進行比較，如果相同就真，否則，假！
將問題轉化成倆棵樹是否相同的比較！
代碼：
bool SameTree(struct TreeNode*q,struct TreeNode*p)
{if(q==NULL&&p==NULL)return true;if(q==NULL||p==NULL)return false;if(q->val!=p->val)return false;return SameTree(q->left,p->left)&&SameTree(q->right,p->right);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){//找出所有子樹，再和另一棵子樹比較是否相同if(root==NULL)return false;//值相等時，開始比較樹是否相等if(root->val==subRoot->val&&SameTree(root,subRoot))return true;//在左子樹和右子樹中能找到就行return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}二叉樹的構建和遍歷
題目：
詳情：二叉樹的構建和遍歷_牛客網
思路：
遍歷讀取數組的每個值，前序遍歷將樹建好，最后中序遍歷二叉樹打印！
代碼：
#include <stdio.h>
#include<stdlib.h>
typedef struct TreeNode {struct TreeNode* left;struct TreeNode* right;char val;
} TNode;
void Inoder(TNode*root)
{if(root==NULL)return;Inoder(root->left);printf("%c ",root->val);Inoder(root->right);
}
TNode*CreateTree(char*a,int*i)
{if(a[(*i)]=='#'){(*i)++;return NULL;}TNode*node=(TNode*)malloc(sizeof(TNode));node->val=a[(*i)++];node->left=CreateTree(a, i);node->right=CreateTree(a, i);return node;
}
int main() {char a[100];scanf("%s",a);int i=0;TNode*root=CreateTree(a,&i);Inoder(root);return 0;
}翻轉二叉樹
題目：
詳情：翻轉二叉樹_LeetCode
思路：
遞歸，先將左子樹交換，再將右子樹交換！
代碼：
struct TreeNode* invertTree(struct TreeNode* root) {if(root==NULL)return NULL;struct TreeNode*tmp;tmp=root->left;root->left=root->right;root->right=tmp;//交換左子樹if(root->left)invertTree(root->left);//交換右子樹if(root->right)invertTree(root->right);return root;
}判斷平衡二叉樹
題目：
詳情：平衡二叉樹_LeetCode
代碼：
int TreeHeight(struct TreeNode* p) {if (p == NULL)return 0;int leftheight = TreeHeight(p->left);int rightheight = TreeHeight(p->right);return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
}
bool isBalanced(struct TreeNode* root) {if (root == NULL)return true;return isBalanced(root->left) && isBalanced(root->right)&&abs(TreeHeight(root->left) - TreeHeight(root->right)) <= 1;
}今天的題目，你都學會了嗎？我們下期見！
)
)
