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

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

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


对于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

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

            </div>
目录
相关文章
|
1月前
力扣面试经典题之二叉树
力扣面试经典题之二叉树
22 0
|
1月前
数据结构之二叉树及面试题讲解(二)
数据结构之二叉树及面试题讲解
33 0
|
29天前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
29天前
【一刷《剑指Offer》】面试题 19:二叉树的镜像
【一刷《剑指Offer》】面试题 19:二叉树的镜像
|
30天前
【一刷《剑指Offer》】面试题 6:重建二叉树
【一刷《剑指Offer》】面试题 6:重建二叉树
|
1月前
|
算法 C++
数据结构和算法面试题:实现一个函数,将一棵二叉树转换为它的镜像。(递归或者非递归实现)
数据结构和算法面试题:实现一个函数,将一棵二叉树转换为它的镜像。(递归或者非递归实现)
21 0
|
1月前
|
算法 Java C++
数据结构与算法面试题:实现二叉树的遍历(前序、中序、后序、层序)。
数据结构与算法面试题:实现二叉树的遍历(前序、中序、后序、层序)。
28 0
【面试小知识】带你深入了解二叉树的前中序遍历
【面试小知识】带你深入了解二叉树的前中序遍历
|
1月前
|
算法 Java 程序员
【Java程序员面试专栏 数据结构篇】五 高频面试算法题:二叉树
【Java程序员面试专栏 数据结构篇】五 高频面试算法题:二叉树
43 0
|
6月前
|
算法 C语言 C++
LeetCode | 二叉树高频面试算法题汇总【速来】-2
LeetCode | 二叉树高频面试算法题汇总【速来】
40 0