目錄
1. 單值二叉樹
2. 檢查兩顆樹是否相同
3. 對稱二叉樹
4. 二叉樹的前序遍歷
5. 二叉樹的中序遍歷
6. 二叉樹的后序遍歷
7. 另一顆樹的子樹
8. 二叉樹的結(jié)構(gòu)及遍歷
世界上沒有不勞而獲的東西！
1. 單值二叉樹
鏈接：力扣
代碼1：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
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);
}思想：（1）【左孩子的返回值是否相等+右孩子的返回值是否相等】當(dāng)左孩子和根比較不相等或者右孩子和根比較不相等，這個樹就是不相等的【返回true的條件比較多，所以，返回不相等的條件少】【代碼1】（2）遍歷，和根的值進行比較
注意：（1）在OJ題中盡量不要定義靜態(tài)變量和全局變量
2. 檢查兩顆樹是否相同
鏈接：力扣
代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-568398.html
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
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);
}思想：遞歸；分治
3. 對稱二叉樹
鏈接：力扣
代碼：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool _isSymmetric(struct TreeNode* p, struct TreeNode* q)
{
//
if (p == NULL && q == NULL)
{
return true;
}
//其中一個為空
if (p == NULL || q == NULL)
{
return false;
}
return p->val == q->val && _isSymmetric(p->left, q->right) && _isSymmetric(p->right, q->left);
}
bool isSymmetric(struct TreeNode* root)
{
if (root == NULL)
{
return true;
}
return _isSymmetric(root->left, root->right);
}思想：首先，判斷樹的左子樹和右子樹是否相等；然后，判斷左子樹的左子樹和右子樹的右子樹以及左子樹的右子樹和右子樹的左子樹是否相等，以及重復(fù)這個操作
4. 二叉樹的前序遍歷
鏈接：力扣
代碼：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
//意思是返回值可以被malloc，假設(shè)由調(diào)用者釋放
*/
//首先確定二叉樹的節(jié)點個數(shù)
int BinaryTreeSize(struct TreeNode* root)
{
return root == NULL ? 0 : (BinaryTreeSize(root->left)+BinaryTreeSize(root->right) + 1);
}
int* preorder(struct TreeNode* root, int* a, int* pi)
{
if (root == NULL)
{
return;
}
a[*pi] = root->val;
(*pi)++;
preorder(root->left, a, pi);
preorder(root->right, a, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
//定義的是數(shù)組的指針，因為定義的如果是數(shù)組，出了這個函數(shù)，就被銷毀了
int size = BinaryTreeSize(root);//j節(jié)點個數(shù)
int* a = (int*)malloc(sizeof(int) * size);//定義數(shù)組
if (a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
*returnSize = size;
//前序遍歷，并把結(jié)果，給數(shù)組,
int i = 0;
preorder(root,a, &i);
return a;
}思想：首先，我們可以非常容易地想到前序遍歷的，把之前學(xué)到過的前序遍歷的printf，改成數(shù)組的賦值。看題意，我們需要定義一個數(shù)組的指針和二叉樹的節(jié)點個數(shù)，然后盡可以調(diào)用前序遍歷的函數(shù)，進行解決。
注意：returnSize?這個代表的是數(shù)組的大小，這個函數(shù)，相當(dāng)于輸出型參數(shù)，returnSize，外面定義了，但是沒有值，需要我們對齊進行賦值?！具@里應(yīng)該用指針，因為形參的改變并不影響實參】
5. 二叉樹的中序遍歷
鏈接：力扣
代碼：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int BinaryTreeSize(struct TreeNode* root)
{
return root == NULL ? 0 : (BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1);
}
void inorder(struct TreeNode* root, int* a, int* pi)
{
if (root == NULL)
{
return;
}
inorder(root->left, a, pi);
a[*pi] = root->val;
(*pi)++;
inorder(root->right, a, pi);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
int size = BinaryTreeSize(root);
*returnSize = size;
int* a = (int*)malloc(sizeof(int) * size);
if (a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
int i = 0;
inorder(root, a, &i);
return a;
}6. 二叉樹的后序遍歷
鏈接：力扣
代碼：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int BinaryTreeSize(struct TreeNode* root)
{
return root == NULL ? 0 : (BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1);
}
void postorder(struct TreeNode* root, int* a, int* pi)
{
if (root == NULL)
{
return;
}
postorder(root->left, a, pi);
postorder(root->right, a, pi);
a[*pi] = root->val;
(*pi)++;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize)
{
int size = BinaryTreeSize(root);
*returnSize = size;
int* a = (int*)malloc(sizeof(int) * size);
int i = 0;
postorder(root, a, &i);
return a;
}7. 另一顆樹的子樹
鏈接：力扣
代碼：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
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;
}
return isSameTree(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}思想：分治，根中是否有和subRoot相等+左子樹中是否有和subRoot相等的部分+左子樹中是否有和subRoot相等的部分。
注意：主函數(shù)中，我們可能會漏掉if這個條件語句，如果不寫這個代碼，root->left，就會出現(xiàn)問題。
8. 二叉樹的結(jié)構(gòu)及遍歷
鏈接：?？?/p>
代碼：
#include <stdio.h>
#include <stdlib.h>
typedef struct BinaryTreeNode
{
char data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
//先構(gòu)建一個二叉樹【前序遍歷】
BTNode* CreatTree(char* a, int* pi)
{
if (a[*pi] == '#')
{
(*pi)++;
return NULL;
}
//先構(gòu)建根
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
root->data = a[*pi];
(*pi)++;
//再構(gòu)建左子樹和右子樹
root->left = CreatTree(a, pi);
root->right = CreatTree(a, pi);
return root;
}
void InOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}
int main()
{
char a[100];
scanf("%s", a);
int i = 0;
BTNode* tree = CreatTree(a, &i);
InOrder(tree);
free(tree);
tree = NULL;
return 0;
}思想：先序遍歷的思想的字符串，建立二叉樹【遇到'#',就返回NULL】，然后再中序遍歷的思想進行打印。文章來源地址http://www.zghlxwxcb.cn/news/detail-568398.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】二叉樹基礎(chǔ)OJ的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
