牛客网《剑指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​

  ​