力扣做题记录 （二叉树）

二叉树

打算先来了解二叉树基础，都是简单题，目的是熟悉代码格式和解题基础思路。

1、二叉树最大深度

二叉树最大深度

方法一、深度搜索

直接用原函数做递归，比较简单

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root ==nullptr)return 0;
        return max(maxDepth(root->left), maxDepth(root->right))+1;
    }
};

方法二、广度搜索

• 利用queue来存储每一层的节点
• 每层次循环是当前queue的长度，用一个数来记录，一般是2的次方，然后再将新的数放置queue末尾。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==nullptr)return 0;
        queue<TreeNode*> Q;
        Q.push(root);
        int depth = 0;
        while(!Q.empty()){
            int sz=Q.size();
            while(sz>0){
                TreeNode* node= Q.front();
                Q.pop();
                if(node->left)Q.push(node->left);
                if(node->right)Q.push(node->right);
                sz-=1;
            }
            depth+=1;
        }
        return depth;
    }
};

2、相同的树

相同的树

方法一、前序遍历比较

这是自己写的，思路是确定可以用递归，这个是深度搜索
然后先判断节点存在，再判断是否正确

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        bool a=true,b=true;
        if(p==nullptr&&q==nullptr)return true;
        else if(p!=nullptr&&q==nullptr)return false;
        else if(p==nullptr&&q!=nullptr)return false;
        else{
            if(p->val!=q->val)return false;
            a=isSameTree(p->left,q->left);
            b=isSameTree(p->right,q->right);
        }
        if(a==false||b==false)return false;
        else return true;
    }
};

方法二、广度搜索

来自官方题解中的一种有点复杂。

class Solution {  
public:  
    // 检查两棵二叉树是否相同  
    bool isSameTree(TreeNode* p, TreeNode* q) {  
        // 如果两棵树都为空，返回 true  
        if (p == nullptr && q == nullptr) {  
            return true;  
        }   
        // 如果一棵树为空而另一棵树不为空，返回 false  
        else if (p == nullptr || q == nullptr) {  
            return false;  
        }  

        // 创建两个队列用于广度优先搜索（BFS）  
        queue<TreeNode*> queue1, queue2;  
        queue1.push(p); // 将第一个树的根节点入队  
        queue2.push(q); // 将第二个树的根节点入队  

        // 当两个队列都不为空时，继续比较  
        while (!queue1.empty() && !queue2.empty()) {  
            // 取出两个队列的前端节点进行比较  
            auto node1 = queue1.front();  
            queue1.pop();  
            auto node2 = queue2.front();  
            queue2.pop();  

            // 比较两个节点的值  
            if (node1->val != node2->val) {  
                return false; // 值不相同，则树不相同  
            }  

            // 获取当前节点的左右子节点  
            auto left1 = node1->left, right1 = node1->right;  
            auto left2 = node2->left, right2 = node2->right;  

            // 检查左右子节点是否存在不一致  
            if ((left1 == nullptr) ^ (left2 == nullptr)) {  
                return false; // 只有一棵树有左子节点  
            }  
            if ((right1 == nullptr) ^ (right2 == nullptr)) {  
                return false; // 只有一棵树有右子节点  
            }  

            // 如果左右子节点存在，则将其加入队列中  
            if (left1 != nullptr) {  
                queue1.push(left1); // 将第一个树的左子节点添加到队列  
            }  
            if (right1 != nullptr) {  
                queue1.push(right1); // 将第一个树的右子节点添加到队列  
            }  
            if (left2 != nullptr) {  
                queue2.push(left2); // 将第二个树的左子节点添加到队列  
            }  
            if (right2 != nullptr) {  
                queue2.push(right2); // 将第二个树的右子节点添加到队列  
            }  
        }  

        // 返回两个队列是否都为空（即两棵树的结构是否相同）  
        return queue1.empty() && queue2.empty();  
    }  
};

3、翻转二叉树

翻转二叉树

方法一、

用递归找到最下方的左右子树，直接更换节点而不是值

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==nullptr){
            return nullptr;
        }
        TreeNode *left=invertTree(root->left);
        TreeNode *right=invertTree(root->right);
        root->left=right;
        root->right=left;
        return root;
    }
};

4、对称二叉树

101.对称二叉树

方法一、广度匹配

也就是迭代求解，下面是我自己写的复杂的代码，因为本能觉得可以把每一层，存储为一个vector，然后再综合比较。但是实现起来略显复杂

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> tree_level;
        vector<int> num_level;
        vector<int> num_level_re;
        int level=1;
        if(root->left==nullptr&&root->right==nullptr)return true;
        else if(root->left!=nullptr&&root->right!=nullptr){level=1;}
        else return false;
        tree_level.push(root->left);
        num_level.push_back(root->left->val);
        tree_level.push(root->right);
        num_level.push_back(root->right->val);
        while(tree_level.size()!=0){
            num_level_re=num_level;
            reverse(num_level_re.begin(),num_level_re.end());
            for(int i=0;i<num_level.size();i++){
                if(num_level[i]==num_level_re[i])continue;
                else return false;
            }
            num_level.clear();
            num_level_re.clear();
            // 把每层都节点和元素加入
            int level1 = tree_level.size();
            while(level1>0){
                TreeNode* root_now;
                root_now = tree_level.front();
                tree_level.pop();
                if(root_now->left!=nullptr){tree_level.push(root_now->left);num_level.push_back(root_now->left->val);}
                else num_level.push_back(-1);
                if(root_now->right!=nullptr){tree_level.push(root_now->right);num_level.push_back(root_now->right->val);}
                else num_level.push_back(-1);
                level1--;
            }
            // 判断每层不能为奇数
            if(tree_level.size()%2!=0)return false;  
            level++;
        }
        return true;
    }
};

方法二、精简迭代法

其思路是：特地写一个辅助函数，可以同时输入左右子树，这样更加方便做迭代

class Solution {
public:
    bool check(TreeNode *u, TreeNode *v) {
        queue <TreeNode*> q;
        q.push(u); q.push(v);
        while (!q.empty()) {
            u = q.front(); q.pop();
            v = q.front(); q.pop();
            if (!u && !v) continue;
            if ((!u || !v) || (u->val != v->val)) return false;

            q.push(u->left); 
            q.push(v->right);

            q.push(u->right); 
            q.push(v->left);
        }
        return true;
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

方法三、递归法

比较难想到，下面是解释
也需要辅助函数， 然后最左的和最右的分别组成对对比

class Solution {
public:
    // 辅助函数：检查两个子树是否对称
    bool check(TreeNode *leftNode, TreeNode *rightNode) {
        // 情况 1：两个节点都为空
        if (leftNode == nullptr && rightNode == nullptr) {
            return true; // 空节点是对称的
        }
        // 情况 2：其中一个节点为空，另一个不为空
        if (leftNode == nullptr || rightNode == nullptr) {
            return false; // 不对称
        }
        // 情况 3：两个节点的值不相等
        if (leftNode->val != rightNode->val) {
            return false; // 不对称
        }
        // 递归检查：
        // 1. 左子树的左节点和右子树的右节点是否对称
        // 2. 左子树的右节点和右子树的左节点是否对称
        bool isOuterSymetric = check(leftNode->left, rightNode->right);  // 检查外层
        bool isInnerSymetric = check(leftNode->right, rightNode->left); // 检查内层
        // 只有外层和内层都对称，整个树才对称
        return isOuterSymetric && isInnerSymetric;
    }
    // 主函数：判断二叉树是否对称
    bool isSymmetric(TreeNode* root) {
        // 如果根节点为空，直接返回 true（空树是对称的）
        if (root == nullptr) {
            return true;
        }
        // 检查左子树和右子树是否对称
        return check(root->left, root->right);
    }
};