牛客網《劍指offer》專欄刷題練習之二叉樹合集

✅作者簡介：熱愛後端語言的大學生

二叉樹題解目錄

• ​​🔥前言​​
• ​​1、二叉樹的下一個結點​​

• ​​1.1、題目速覽​​
• ​​1.2、個人題解​​

• ​​1.2.1、解題思路​​
• ​​1.2.2、代碼實作​​
• ​​1.2.3、代碼解析​​

• ​​2、對稱的二叉樹​​

• ​​2.1、題目速覽​​
• ​​2.2、個人題解​​

• ​​2.2.1、解題思路​​
• ​​2.2.2、代碼實作​​
• ​​2.2.3、代碼解析​​

🔥前言

本篇文章給大家分享牛客網《劍指offer》專欄中有關二叉樹的經典算法題解，我會按照自己的了解與思路幫助大家搞懂算法流程。

1、二叉樹的下一個結點

1.1、題目速覽

1.2、個人題解

1.2.1、解題思路

1. 我們首先要根據給定輸入中的結點指針向父級進行疊代，直到找到該樹的根節點；

2. 然後根據根節點進行中序周遊，當周遊到和給定樹節點相同的節點時，下一個節點就是我們的目标傳回節點

具體步驟：

1. 根據目前結點，利用題目所給條件找到根結點
2. 書寫中序周遊的函數，傳入根結點
3. 将中序周遊的結點儲存在結點數組裡
4. 将傳入的二叉樹結點與數組元素比對，傳回數組的下一個元素

1.2.2、代碼實作

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
class Solution {
public:
    vector<TreeLinkNode*>nodes;
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        TreeLinkNode* root=pNode;
        //利用父指針找到根結點
        while(root->next)    
            root=root->next;
        //調用中序周遊
        InOrder(root);
        int num=nodes.size();
        for(int i=0;i<num;i++){
            TreeLinkNode *cur=nodes[i];
            if(pNode==cur){
                return nodes[i+1];
            }
        }
        return NULL;
    }
    //書寫中序周遊
    void InOrder(TreeLinkNode* root){
        if(root==NULL) return;
        InOrder(root->left);
        nodes.push_back(root);
        InOrder(root->right);
    }
};      

1.2.3、代碼解析

• 首先建立動态數組​

  ​nodes​

  ​，注意是建立在方法外部，目的是可以在類内任意使用
• 建立的​

  ​root​

  ​​結點并借助​

  ​while​

  ​​循環通過父指針​

  ​next​

  ​找到根結點
• 書寫​

  ​InOrder​

  ​​中序周遊函數，将中序周遊結果存入上方建立的​

  ​nodes​

  ​數組中
• 使用​

  ​for​

  ​​循環将傳入結點​

  ​pNode​

  ​與數組元素比較，如果比對到就傳回位置加一的結點

2、對稱的二叉樹

2.1、題目速覽

2.2、個人題解

2.2.1、解題思路

1. 兩種方向的前序周遊，同步過程中的目前兩個節點，同為空，屬于對稱的範疇。
2. 目前兩個節點隻有一個為空或者節點值不相等，已經不是對稱的二叉樹了。
3. 第一個節點的左子樹與第二個節點的右子樹同步遞歸對比，第一個節點的右子樹與第二個節點的左子樹同步遞歸比較。

2.2.2、代碼實作

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot) {
        return dgfunc(pRoot,pRoot);
    }
    bool dgfunc(TreeNode* root1,TreeNode* root2){
        if(root1==NULL&&root2==NULL)
            return true;
        if(root1==NULL||root2==NULL||root1->val!=root2->val)
            return false;
        return dgfunc(root1->left, root2->right) && dgfunc(root1->right,root2->left);
    }
};      

2.2.3、代碼解析

• 編寫​

  ​dgfunc​

  ​​函數，将​

  ​pRoot​

  ​傳入比較
• 前兩個if是遞歸結束的條件：

• 如果結點相同傳回​

  ​true​

  ​
• 如果一邊為​

  ​NULL​

  ​​或者左子樹與右子樹不同，傳回​

  ​false​

  ​

• 調用遞歸，比較左右子樹，都相同就傳回​

  ​true​

  ​​，不相同則傳回​

  ​false​

  ​