面试热点|二叉树那点事儿(一)下

简介: 前面写了很多篇工程相关的文章,今天准备写个数据结构和算法相关的文章。

0x04.其他两道题目的糙代码


对于LeetCode第100题相同的树和LeetCode第101题镜像树,笔者均用相同的路子进行解决,可以看下具体的实现。


4.1 第100题相同的树


23.png

具体代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    //虽然该题目是easy 但是为了尽量多的练习 实用了非递归中序遍历(包含空节点)、vector、queue、迭代器的基本用法
    void travese(TreeNode *root, vector<string> &vec)
    {
        //选择非递归层次遍历
        TreeNode *node = root;
        queue<TreeNode*> q;
        q.push(node);
        while(!q.empty())
        {
            TreeNode *top = q.front();
            if(top){
                //左结点
                if(top->left)
                    q.push(top->left);
                else
                    q.push(NULL);
                //右节点
                if(top->right)
                    q.push(top->right);
                else
                    q.push(NULL);
                q.pop();
                vec.push_back(std::to_string(top->val));
            }else{
                q.pop();
                vec.push_back("null");
            }
        }
    }
    //遍历vector对比
    bool comp(vector<string> &vecp, vector<string> &vecq){
        vector<string>::iterator iterp = vecp.begin();
        vector<string>::iterator iterq = vecq.begin();
        if(vecq.size()!=vecp.size())
            return false;
        for(;iterp!=vecp.end(),iterq!=vecq.end();iterp++,iterq++){
            if(*iterp == *iterq)
                continue;
            else
                return false;
        }
        return true;
    }
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p&&!q)
            return true;
        if(!q||!p)
            return false;
        //两棵树都非空的前提下
        vector<string> vecp;
        vector<string> vecq;
        travese(p,vecp);
        travese(q,vecq);
        return comp(vecp,vecq);
    }
};


4.2 第101题镜像树

24.png

具体代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    //从左到右层次遍历
    void travese(TreeNode *root, vector<string> &vec)
    {
        //选择非递归层次遍历
        TreeNode *node = root;
        queue<TreeNode*> q;
        q.push(node);
        while(!q.empty())
        {
            TreeNode *top = q.front();
            if(top){
                //左结点
                if(top->left)
                    q.push(top->left);
                else
                    q.push(NULL);
                //右节点
                if(top->right)
                    q.push(top->right);
                else
                    q.push(NULL);
                q.pop();
                vec.push_back(std::to_string(top->val));
            }else{
                q.pop();
                vec.push_back("null");
            }
        }
    }
    //从右到左层次遍历
    void revtravese(TreeNode *root, vector<string> &vec)
    {
        //选择非递归层次遍历
        TreeNode *node = root;
        queue<TreeNode*> q;
        q.push(node);
        while(!q.empty())
        {
            TreeNode *top = q.front();
            if(top){
                //右结点
                if(top->right)
                    q.push(top->right);
                else
                    q.push(NULL);
                //左节点
                if(top->left)
                    q.push(top->left);
                else
                    q.push(NULL);
                q.pop();
                vec.push_back(std::to_string(top->val));
            }else{
                q.pop();
                vec.push_back("null");
            }
        }
    }
    bool isSymmetric(TreeNode* root) {
        //空树或者只有根节点的树
        if(!root||(root->left==NULL&&root->right==NULL))
            return true;
        //其他情况
        vector<string> vecleft;
        vector<string> vecright;
        travese(root,vecleft);
        revtravese(root,vecright);
        return vecleft==vecright;
    }
};



0x05.笔者小结


写到这里基本上就到尾声了,简单总结一下:


本文通过3道二叉树的问题展开,目前是让我们获得一种在紧张场合快速切入解题的思路,其中涉及到一些自己的习惯可能并不为很多人接受,其次笔者本着一道题复习多个知识点的原则实现了很长的代码,无他就是为了练习。


做LeetCode就像现在手机厂商发布会上跑个分看看,亮一亮时间和空间碾压了多少人,漂亮简洁的算法确实让人惊艳,但是其背后凝结了无数的糙代码

25.png

道阻且长 戒骄戒躁 扎好马步 我们也可以练就九阳神功!

相关文章
|
2月前
力扣面试经典题之二叉树
力扣面试经典题之二叉树
24 0
|
2月前
数据结构之二叉树及面试题讲解(二)
数据结构之二叉树及面试题讲解
33 0
|
10月前
|
存储 算法
【数据结构】 二叉树面试题讲解->叁
【数据结构】 二叉树面试题讲解->叁
|
10月前
|
存储
【数据结构】 二叉树面试题讲解->壹I(二)
【数据结构】 二叉树面试题讲解->壹I(二)
|
11月前
|
JSON 前端开发 JavaScript
探究JavaScript前端热点面试题(三):让你在面试中游刃有余!
探究JavaScript前端热点面试题(三):让你在面试中游刃有余!
|
2月前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
2月前
【一刷《剑指Offer》】面试题 19:二叉树的镜像
【一刷《剑指Offer》】面试题 19:二叉树的镜像
|
2月前
【一刷《剑指Offer》】面试题 6:重建二叉树
【一刷《剑指Offer》】面试题 6:重建二叉树
|
2月前
|
算法 C++
数据结构和算法面试题:实现一个函数,将一棵二叉树转换为它的镜像。(递归或者非递归实现)
数据结构和算法面试题:实现一个函数,将一棵二叉树转换为它的镜像。(递归或者非递归实现)
24 0
|
2月前
|
算法 Java C++
数据结构与算法面试题:实现二叉树的遍历(前序、中序、后序、层序)。
数据结构与算法面试题:实现二叉树的遍历(前序、中序、后序、层序)。
29 0