前言

筆者終于期末考完回來啦！力扣系列終于可以重新開始更新了惹~

本來是打算把二叉樹也作為每日一題每天更新多水幾篇文章，咳咳，多寫幾天的，畢竟一口吃不成一個胖子嘛，凡是都要慢慢來是吧，但是這個坑留的越久，以后內容多了這個坑就填不起來了，所以今天就統一暴力一點，把這個坑填上了

以下的oj題都是二叉樹的基本題目，基本都涉及了遞回和分治的思想

單值二叉樹

原題鏈接

題目描述

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

例如：
上圖就是一顆單值二叉樹

思路求解

我們在這篇文章中可以繼續采用分而治之的思想

我們可以檢查，只要樹的左子樹和右子樹和根的值相同就行了

檢查左子樹和右子樹時，同樣，只需檢查左右子樹的左右子樹是否與它們相同就行了

動圖：

代碼實作

bool isUnivalTree(struct TreeNode* root){
    if(!root)
        return true;//空樹也算單值二叉樹，還有就是可以一直遍歷到最后一層回傳true
    if(root->left&&root->val!=root->left->val)
        return false;
    if(root->right&&root->val!=root->right->val)
        return false;//不等于的直接回傳false
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

二叉樹的最大深度

原題鏈接

題目描述

給定一個二叉樹，找出其最大深度，
二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數，
說明: 葉子節點是指沒有子節點的節點，

例如：

有三層，所以回傳3

思路求解

我們要做這道題，只需要算出左右子樹中哪個深度較大，最后在加上根結點，也就是較大深度+1，左右子樹使用同樣的演算法

動圖：

代碼實作：

int maxDepth(struct TreeNode* root){
    if(!root)
        return 0;
    if(root->left==root->right)
        return 1;
    int leftDepth=maxDepth(root->left);
    int rightDepth=maxDepth(root->right);//用中間變數保存，防止遞回次數過多

    return leftDepth>rightDepth?leftDepth+1:rightDepth+1;
}

翻轉二叉樹

原題鏈接

題目描述

思路求解

根據題意，我們可以觀察到所謂的翻轉就是將左子樹和右子樹的結點相互交換，同樣，左子樹和右子樹的子樹也同樣需要交換，

這里需要判斷幾種情況：

為葉子結點時，也就是左右子樹均為空，不需要交換，直接回傳結點即可

空樹直接回傳空

其它情況直接交換即可

難度不大，直接按著思路寫代碼即可

struct TreeNode* invertTree(struct TreeNode* root){
    struct TreeNode* ret=root;
    if(!root)
        return NULL;
    if(root->left==root->right)
        return root;
    struct TreeNode* tmp=root->left;
    root->left=root->right;
    root->right=tmp;//這里是交換左右

    invertTree(root->left);//遞回下去交換即可
    invertTree(root->right);

    return root;
}

二叉樹的前序遍歷

原題鏈接

題目描述

給你二叉樹的根節點 root ，回傳它節點值的 前序 遍歷，

例如：

回傳：1，2，3

注意，本題需要陣列存盤遍歷出的值

思路求解

既然需要陣列存盤資料，所以我們必須要知道我們要開辟多少空間
所以我們第一步就需要計算出這個二叉樹有多大，（在二叉樹基礎中我已經介紹了演算法，所以這里不再闡述）

但難點就是遍歷樹的時候（遞回的時候）陣列下標中i的控制

因為函式出了作用域后區域變數的值會被銷毀，但遞回需要呼叫很多次，所以需要保存i此時的值，就需要用到指標來控制了

知道了這個，這題就能輕松求出來

void _PrevOrder(struct TreeNode* root,int* arr,int* i)//遍歷子函式
{
    if(!root)
        return;
    arr[(*i)++]=root->val;
    _PrevOrder(root->left,arr,i);
    _PrevOrder(root->right,arr,i);

}

int BinTreeSize(struct TreeNode* root)//求樹的大小
{
    if(!root)
        return 0;
    return BinTreeSize(root->left)+BinTreeSize(root->right)+1;
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize=BinTreeSize(root);

    int* arr=(int*)malloc(sizeof(int)*(*returnSize));

    int i=0;
    _PrevOrder(root,arr,&i);
    return arr;
}

檢查兩棵樹是否相同

原題鏈接

題目描述

給你兩棵二叉樹的根節點 p 和 q ，撰寫一個函式來檢驗這兩棵樹是否相同，
如果兩個樹在結構上相同，并且節點具有相同的值，則認為它們是相同的，

例如：

這兩棵樹相同

這兩棵樹不同

思路求解

這題同樣使用上面用到的分治思想，有以下幾種情況

p和q樹都為空，兩棵樹肯定相同

其中有一個都不為空都不相同

其實有一個結點不相同都不是相同的

然后順序往下找即可

代碼實作

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(!p&&!q)
        return true;
    if(!p&&q)
        return false;
    if(p&&!q)
        return false;
    if(p->val!=q->val)
        return false;

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

平衡二叉樹

原題鏈接

題目描述

給定一個二叉樹，判斷它是否是高度平衡的二叉樹，

本題中，一棵高度平衡二叉樹定義為：
一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1 ，

例如：

是平衡二叉樹

思路求解

首先，這道題涉及到求深度，所以需要用到我們在二叉樹基礎中用過的判斷深度的函式

需要深度之差不超過1，只需要用到abs函式來判斷

其中，只要深度之差超過2，立刻回傳false
直到將全樹遞回完為止

代碼實作

int maxDepth(struct TreeNode* root){
    if(!root)
        return 0;
    int left=maxDepth(root->left);
    int right=maxDepth(root->right);
    return left>right ? left+1 :right+1;
}//判斷深度的函式
bool isBalanced(struct TreeNode* root){
    if(!root)
        return true;
    int left=maxDepth(root->left);
    int right=maxDepth(root->right);
    return abs(left-right)<2
    &&isBalanced(root->left)
    &&isBalanced(root->right);//絕對值小于2，以及左右子樹同時為平衡二叉樹，才為真，否則為假
}

另一顆樹的子樹

原題鏈接

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

例如：

思路求解

我們在這里，如果需要判斷是否有子樹，首先需要一個判斷樹是否相同的函式

在遞回中也分幾種情況

空樹肯定沒有子樹，回傳false

找到相同的子樹后，回傳true

本題是找子樹，只需要左右只有一個子樹就行了，也就是用或運算子

代碼實作

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(!p&&!q)
        return true;
    if(!p&&q)
        return false;
    if(p&&!q)
        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)
        return false;//空樹肯定沒有子樹，回傳false
    if(isSameTree(root,subRoot))
        return true;
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

對稱二叉樹

原題鏈接

給定一個二叉樹，檢查它是否是鏡像對稱的，

例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的，

思路求解

這里與判斷二叉樹相同相似，只需要將左右子樹當作兩顆不同的樹來比較即可

但是這里的比較跟判斷相同還是有點區別的

根據鏡像對稱的特點，這里需要左子樹與右子樹對比，右子樹與左子樹對比

代碼實作

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(!p&&!q)
        return true;
    if(!p&&q)
        return false;
    if(p&&!q)
        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)
        return true;
    return isSameTree(root->left,root->right);
}