前言

??個(gè)人主頁(yè)：@小沈熬夜禿頭中????
??小編介紹：歡迎來(lái)到我的亂七八糟小星球??
??專(zhuān)欄：力扣—LeetCode刷題
??本章內(nèi)容：力扣—二叉樹(shù)OJ題
送給各位??：活著就意味著要必須做點(diǎn)什么 請(qǐng)好好努力
歡迎 評(píng)論?? +點(diǎn)贊?? +收藏?? +關(guān)注??哦~

提示：以下是本篇文章正文內(nèi)容，下面案例可供參考

??一、劍指 Offer 55 - I. 二叉樹(shù)的深度

輸入一棵二叉樹(shù)的根節(jié)點(diǎn)，求該樹(shù)的深度。從根節(jié)點(diǎn)到葉節(jié)點(diǎn)依次經(jīng)過(guò)的節(jié)點(diǎn)（含根、葉節(jié)點(diǎn)）形成樹(shù)的一條路徑，最長(zhǎng)路徑的長(zhǎng)度為樹(shù)的深度。
例如：
給定二叉樹(shù) [3,9,20,null,null,15,7]，
返回它的最大深度 3 。

??1.1 鏈接：

劍指 Offer 55 - I. 二叉樹(shù)的深度

??1.2 代碼一：

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

??1.3 代碼二：

這種代碼是正確的但是在力扣上是不能通過(guò)的時(shí)間太長(zhǎng)具體分析可以看【數(shù)據(jù)結(jié)構(gòu)】—幾分鐘簡(jiǎn)單幾步學(xué)會(huì)手撕鏈?zhǔn)蕉鏄?shù)(中)中求二叉樹(shù)高度部分

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

??1.4 流程圖：

??二、100. 相同的樹(shù)

給你兩棵二叉樹(shù)的根節(jié)點(diǎn) p 和 q ，編寫(xiě)一個(gè)函數(shù)來(lái)檢驗(yàn)這兩棵樹(shù)是否相同。
如果兩個(gè)樹(shù)在結(jié)構(gòu)上相同，并且節(jié)點(diǎn)具有相同的值，則認(rèn)為它們是相同的。

??2.1 鏈接：

100. 相同的樹(shù)

??2.2 思路：

采用前序,先比較 根 然后 左子樹(shù) 右子樹(shù)，而結(jié)束條件就是為空樹(shù)或者不相等

??2.3 代碼：

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    if(p==NULL&&q==NULL)//兩者都為空樹(shù)則表示相同
    return true;
    if(p==NULL||q==NULL)//有一個(gè)不為空則不同
    return false;
    if(p->val!=q->val)//數(shù)值不同則不同
    return false;
    return isSameTree(p->left, q->left)&&isSameTree(p->right, q->right);//采用邏輯與當(dāng)左樹(shù)不相同時(shí)，就沒(méi)必要比較右樹(shù)
}

??2.4 流程圖：

??三、965. 單值二叉樹(shù)

如果二叉樹(shù)每個(gè)節(jié)點(diǎn)都具有相同的值，那么該二叉樹(shù)就是單值二叉樹(shù)。
只有給定的樹(shù)是單值二叉樹(shù)時(shí)，才返回 true；否則返回 false。

??3.1 鏈接：

965. 單值二叉樹(shù)

??3.2 思路：

采用傳遞性：ab bc <> ac,然后通過(guò)對(duì)比根節(jié)點(diǎn)和左子樹(shù)，左子樹(shù)，右子樹(shù)來(lái)判斷值是否相同

??3.3 代碼：

bool isUnivalTree(struct TreeNode* root)
{
    if(root==NULL)
    return true;
    if(root->left!=NULL&&root->left->val!=root->val)
    //左子樹(shù)不為空且左子樹(shù)的值和根值不同
    return false;
    if(root->right!=NULL&&root->right->val!=root->val)
    //右子樹(shù)不為空且右子樹(shù)的值和根值不同
    return false;
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

??3.4 流程圖：

??四、101. 對(duì)稱(chēng)二叉樹(shù)

給你一個(gè)二叉樹(shù)的根節(jié)點(diǎn) root ， 檢查它是否軸對(duì)稱(chēng)。

??4.1 鏈接：

101. 對(duì)稱(chēng)二叉樹(shù)

??4.2 思路：

因?yàn)槭?mark>軸對(duì)稱(chēng)，所以要比較左子樹(shù)的值和右子樹(shù)的值相同。

??4.3 代碼：

bool _isSymmetric(struct TreeNode* leftRoot,struct TreeNode* rightRoot)
{
    if(leftRoot==NULL&&rightRoot==NULL)
    return true;
    if(leftRoot==NULL||rightRoot==NULL)
    return false;
    if(leftRoot->val!=rightRoot->val)
    return false;
    return _isSymmetric(leftRoot->left,rightRoot->right)
    &&_isSymmetric(leftRoot->right,rightRoot->left);
}
bool isSymmetric(struct TreeNode* root)
//這個(gè)函數(shù)是題給出的所以不能修改但不符合所以使用返回值
{
//因?yàn)轭}目給出根不為空所以只需要比較左右子樹(shù)就可以了
    return _isSymmetric(root->left,root->right);
}

??4.4 流程圖：

??五、144. 二叉樹(shù)的前序遍歷

??5.1 鏈接：

144. 二叉樹(shù)的前序遍歷

??5.2 代碼(錯(cuò)誤代碼)：

下面這種寫(xiě)法是不能通過(guò)的，因?yàn)槊看握{(diào)用i++,都是各是各的造成了干擾具體可以看流程圖

int TreeSize(struct TreeNode* root)
{
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
void _preorderTraversal(struct TreeNode* root, int* a,int i)
{
    if(root==NULL)
    return;
    a[i++]=root->val;
    _preorderTraversal(root->left,a,i);
    _preorderTraversal(root->right,a,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    *returnSize=TreeSize(root);
    int* a=(int*)malloc(sizeof(int)*(*returnSize));
    int i=0;
    _preorderTraversal(root,a,i);
    return a;
}

??5.3 流程圖：

??5.4 兩種解決方法：

5.4.1??第一種：給i傳地址

??代碼：

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)
{
    *returnSize=TreeSize(root);
    int* a=(int*)malloc(sizeof(int)*(*returnSize));
    int i=0;
    _preorderTraversal(root,a,&i);
    return a;
}

5.4.2??第而種：全局變量

??代碼：

一點(diǎn)注意：要在一次調(diào)用后置零，不然下次調(diào)用時(shí)就會(huì)出現(xiàn)i在上一次的基礎(chǔ)值上接著走而數(shù)組就不是從0開(kāi)始的

int TreeSize(struct TreeNode* root)
{
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
int i=0;
void _preorderTraversal(struct TreeNode* root, int* a)
{
    if(root==NULL)
    return;
    a[i++]=root->val;
    _preorderTraversal(root->left,a);
    _preorderTraversal(root->right,a);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    *returnSize=TreeSize(root);
    int* a=(int*)malloc(sizeof(int)*(*returnSize));
    i=0;//注意這里
    _preorderTraversal(root,a);
    return a;
}

??總結(jié)

??Ending,今天的鏈?zhǔn)蕉鏄?shù)的內(nèi)容就到此結(jié)束啦~，如果后續(xù)想了解更多，就請(qǐng)關(guān)注我吧，一鍵三連哦 ~文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-465080.html

到了這里，關(guān)于力扣---二叉樹(shù)OJ題(多種題型二叉樹(shù))的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！