【LeetCode】——鏈式二叉樹經典OJ題詳解

這篇具有很好參考價值的文章主要介紹了【LeetCode】——鏈式二叉樹經典OJ題詳解。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

?=========================================================================

主頁點擊直達：個人主頁

我的小倉庫：代碼倉庫

C語言偷著笑：C語言專欄

數據結構挨打小記：初階數據結構專欄

Linux被操作記：Linux專欄

LeetCode刷題掉發(fā)記：LeetCode刷題

算法頭疼記：算法專欄?

=========================================================================

前言：

LeetCode 965.單值二叉樹

LeetCode 100.相同的樹

LeetCode 101.對稱二叉樹

LeetCode 144 145 94 .二叉樹的前、中、后序遍歷

LeetCode 572.另一棵樹的子樹

前言：

在之前的文章講解了二叉樹的鏈式結構的實現以及前、中、后序的遍歷。不知道大家看完后有沒有理解和有所收獲，今天基于那篇文章給大家分享講解幾道經典的題目，更便于大家的理解和深入。

二叉樹的題目一定要會兩個思想：

第一個思想：拆分一定要將二叉樹拆分為根、左子樹、右子樹首先就是要判斷根結點是否為空。第二個思想：遞歸，善于使用遞歸。

LeetCode 965.單值二叉樹

OJ鏈接

題目描述：?

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

示例 1：

?
輸入：[1,1,1,1,1,null,1]
輸出：true
示例 2：

?
輸入：[2,2,2,5,2]
輸出：false
審題總結：

判斷一個二叉樹這所有節(jié)點的值是否相等，相等返回true，否則返回false；

思路講解：首先判斷根是否為空，如果為空直接返回true。不為空判斷左子樹是否存在，存在的話判斷和根節(jié)點的值是否相等，如果相等返回true，否則返回false；繼續(xù)判斷右子樹是否存在，存在的話判斷和根節(jié)點的值是否相等，如果相等返回true，否則返回法false。左右子樹都存在的話使用遞歸遍歷。

接口代碼
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 100.相同的樹

OJ鏈接

題目描述：給你兩棵二叉樹的根節(jié)點?p?和?q?，編寫一個函數來檢驗這兩棵樹是否相同

如果兩個樹在結構上相同，并且節(jié)點具有相同的值，則認為它們是相同的。

示例 1：

?
輸入：p = [1,2,3], q = [1,2,3]
輸出：true
示例 2：

?
輸入：p = [1,2], q = [1,null,2]
輸出：false
示例 3：

?
輸入：p = [1,2,1], q = [1,1,2]
輸出：false
思路講解：

先將根拆結點拆分出來，兩個根節(jié)點有三種情況，都為空、兩個根節(jié)點中有一個為空。如果都為空，則返回true；如果有一個為空則返回false。根節(jié)點判斷完成后判斷根節(jié)點的值是否相等；使用遞歸遍歷左子樹和右子樹。

接口代碼
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);
}

LeetCode 101.對稱二叉樹

OJ鏈接

題目描述：

給你一個二叉樹的根節(jié)點?root?，檢查它是否軸對稱。

示例 1：

?
輸入：root = [1,2,2,3,4,4,3]
輸出：true
示例 2：

?
輸入：root = [1,2,2,null,3,null,3]
輸出：falses
思路講解：

這個題目和上個題目非常的相似，還是拆分為根、左子樹、右子樹。這里將兩個子樹看成單獨的樹，就和上面題的思路大差不差了。不同的是要判斷左邊的值和右邊的值是否相等，這樣才算對稱。

實現代碼
 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->right)
    &&isSameTree(p->right,q->left);
    
 }
bool isSymmetric(struct TreeNode* root){
 if(root!=NULL)
 {
     return isSameTree(root->left,root->right);
 }
 else
 return true;
}

LeetCode 144 145 94 .二叉樹的前、中、后序遍歷

前序遍歷OJ鏈接

中序遍歷OJ鏈接

后序遍歷OJ鏈接

關于二叉樹的前、中、后序遍歷的文章點擊直達，這里我不做介紹。由于這三個題目是差不多只是將遍歷的值用數組的形式便是出來，所以我就只講解前序遍歷、中、后序遍歷交給大家練習。

題目描述：給你一棵二叉樹的根節(jié)點?root?，返回其節(jié)點值的?后序遍歷?。

示例 1：

?
輸入：root = [1,null,2,3]
輸出：[3,2,1]
示例 2：
輸入：root = []
輸出：[]
示例 3：
輸入：root = [1]
輸出：[1]
思路講解：

首先求出這棵二叉樹有幾個結點，根據結點動態(tài)開辟相應大小的空間。將根節(jié)點、動態(tài)開辟的數組，變量的地址，交給一個前序遍歷的函數，根據前序遍歷的規(guī)則，進行遞歸給數組賦值。

實現代碼
 int treesize(struct TreeNode*root)
 {
     return root==NULL? 0:treesize(root->left)+treesize(root->right)+1;
 }
 void preoder(struct TreeNode *root,int *a,int *pi)
 {
     if(root==NULL)
     return;
     a[(*pi)++]=root->val;
     preoder(root->left,a,pi);
     preoder(root->right,a,pi);
 }
int* preorderTraversal(struct TreeNode* root, int* returnSize){
     int n=treesize(root);
     int *a=(int *)malloc(sizeof(int )*n);
     int j=0;
    preoder(root,a,&j);
    *returnSize=n;
     return a;
}

LeetCode 572.另一棵樹的子樹

OJ鏈接

題目描述：

給你兩棵二叉樹?root?和?subRoot?。檢驗?root?中是否包含和?subRoot?具有相同結構和節(jié)點值的子樹。如果存在，返回?true?；否則，返回?false?。二叉樹?tree?的一棵子樹包括?tree?的某個節(jié)點和這個節(jié)點的所有后代節(jié)點。tree?也可以看做它自身的一棵子樹。

示例 1：

?
輸入：root = [3,4,5,1,2], subRoot = [4,1,2]
輸出：true
示例 2：?
輸入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
輸出：falses
思路講解：

這個題和上面的LeetCode 100.相同的樹基本上也大差不差。首先判斷根節(jié)點是否為空，如果根節(jié)點為空，則直接返回false；不為空則直接使用是否為相同的樹判斷函數，判斷所給樹是否為子樹，如果為真則直接返回true，使用遞歸遍歷根節(jié)點的左右子樹和所給所給子樹相比較。

實現代碼
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(root->val==subRoot->val)
{
    if(isSameTree(root,subRoot))
    return true;
}
return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);

}