⚓️作者简介：北京某能源高校非科班大四学生。
 
📚座右铭：“九层之台，起于垒土” 。所以学习技术须脚踏实地。
 
📖这里推荐一款刷题、模拟面试神器，可助你斩获大厂offer：点我免费刷题、模拟面试

前言

🌏牛客网是一个集笔面试系统、题库、课程教育、社群交流、招聘内推于一体的招聘类网站，更是一个专注于程序员的学习和成长的平台。
 
在某次浏览博客的过程中，我偶然点进一个链接，注册了牛客账号。一来到牛客首页，我就被其丰富的功能与良好的社区环境所吸引：

进入题库，更是有最新校招试题与专项练习：
在线编程更是有在线调试功能，可大大提高debug效率：

问答题下还有超多牛客用户交流：

🔔总之，牛客是一个专注于程序员的学习和成长的平台，所以我极力推荐大家注册牛客，坚持刷题，充实自己，大厂offer便指日可待。

面试必刷题

 二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。上一节我们练习了二叉树的层序遍历与二叉树转换为双向链表，这一节来刷几个进阶点的题目：

📚

1.对称的二叉树

题目：

示例：

解题思路
这题应该可以用递归写，但上周刷题用的方法大多都是通过队列或栈处理二叉树，所以这题就继续用栈与队列处理。

类比于二叉树的层序遍历，这题也可以利用层序遍历来解，只不过要改变每层的遍历顺序。每次遍历遍历对称的两个节点，判断其左右结构是否对称，再判断值是否对称，若都满足，则当前节点及其父节点都是对称的。

算法流程：

• 对于根节点特殊处理：根节点为空，则是对称的。不空判断左右孩子是否对称，对称则将左右孩子入栈；不对称则该树不对称。

• 栈不空，进入循环1。

  • 栈不空，进入循环2。
  • 连着两个节点出栈，分别保存为node1，node2（根据进队结点的性质，这两个结点是对称结点）。
  • 先判断两个节点结构是否对称，即node1有右孩子同时node2有左孩子，或node1有左孩子同时node2有右孩子。对称则判断数值是否相等，相等则将node1的右孩子，node2的左孩子连续进队，或node2的右孩子，node1的左孩子连续进队。不对称则该树不对称。
  • 回到循环2。

• 将 q 中的节点出队并进栈，回到循环1。

C++解题代码：

/*
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) {
        if (!pRoot || (!pRoot->left && !pRoot->right)) return true;
        if (!pRoot->left || !pRoot->right) return false;
        stack<TreeNode*> s;
        if (pRoot->left->val == pRoot->right->val) {
            s.push(pRoot->left);
            s.push(pRoot->right);
        } else
            return false;
        queue<TreeNode*> q;
        while (!s.empty()) {
            while (!s.empty()) {
                TreeNode* node1 = s.top();
                s.pop();
                if (s.empty())return false;
                TreeNode* node2 = s.top();
                s.pop();
                if (((node1->left && node2->right) || (!node1->left && !node2->right)) &&
                        (node1->right && node2->left || (!node1->right && !node2->left))) {
                    if (node1->left && node2->right) {
                        if (node1->left->val == node2->right->val) {
                            q.push(node1->left);
                            q.push(node2->right);
                        } else return false;
                    }
                    if (node1->right && node2->left) {
                        if (node1->right->val == node2->left->val) {
                            q.push(node1->right);
                            q.push(node2->left);
                        } else return false;
                    }
                }else return false;
            }
            while(!q.empty()) {
                TreeNode* node;
                node = q.front();
                q.pop();
                s.push(node);
            }

        }
        return true;

    }

};

2.二叉树的镜像

题目：

示例：

解题思路
这一题就是利用前序遍历交换两个结点即可，每交换两个结点，结点包括结点的左右孩子也都交换了。递归地交换，即可求得整个二叉树的镜像。

算法流程：

1. 特殊情况：如果pRoot为空，返回空
2. 交换左右子树
3. 把pRoot的左子树镜像一下
4. 把pRoot的右子树镜像一下
5. 返回根节点root

C++解题代码：

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return TreeNode类
     */
    TreeNode* Mirror(TreeNode* pRoot) {
        mirror(pRoot);
        return pRoot;
    }
  private:
    void mirror(TreeNode* pRoot) {
        if (!pRoot) return;
        TreeNode* tmp = pRoot->right;
        pRoot->right = pRoot->left;
        pRoot->left = tmp;
        mirror(pRoot->right);
        mirror(pRoot->left);
    }
};

3.合并二叉树

题目：

示例：

解题思路：
要将一棵二叉树的节点与另一棵二叉树相加合并，肯定需要遍历两棵二叉树，那我们可以考虑同步遍历两棵二叉树，这样就可以将每次遍历到的值相加在一起。遍历的方式有多种，这里推荐前序递归遍历。

算法步骤：

• 以第一个t1为返回树，相加的值存入tree1。

• 如果node1和node2为空，则返回空指针。

• 如果node1不空，node2空，返回node1。

• 如果node1空，node2不空，返回node2。

• 如果都不空则将两个结点值相加存到node1的值中，再merge两棵树的左右子树。

C++解题代码

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        // write code here
        TreeNode *node1 = t1, *node2 = t2;
        return merge(node1, node2);
    }
private:
    TreeNode* merge(TreeNode* node1, TreeNode* node2){
        if(!node1 && !node2) return nullptr;
        if(!node1 && node2) return node2;
        if(node1 && !node2) return node1;
        node1->val += node2->val;
        node1->left = merge(node1->left, node2->left);
        node1->right = merge(node1->right, node2->right);
        return node1;
    }
};

🥇我希望通过写博客来结束浑浑噩噩的生活，我更希望通过刷题结束人云亦云的思考。刷题不仅仅是刷题，还是我们与自己内心深处的对话。希望我们可以一起在牛客刷题交流，一起收割大厂offer！