嵌入式软件常用面试题汇总之 C/C++ 语言相关(6)

C/C++之常考二叉树相关基础编程题汇总

嵌入式的笔试中编程题也会有基础的二叉树相关操作题，以下挑几道当时做过比较基础重要的，掌握了基本就能通关，至少掌握几种遍历的写法。参考的解法都是几年前自己做的了，也欢迎各位优化指正！

1.二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000

解法参考：

/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> result;
        vector<int> tmp;
        if(root == NULL) return result;
        queue<TreeNode*> T;
        T.push(root);
        int size = 0;
        while(!T.empty())
        {   
            size = T.size();
            while(size)
            {
                root = T.front();
                T.pop();
                tmp.push_back(root->val);                
                if(root->left != NULL)
                {
                    //tmp.push_back(root->left->val);
                    T.push(root->left);
                }
                if(root->right != NULL)
                {
                    //tmp.push_back(root->right->val);
                    T.push(root->right);
                }       
                --size;
            }
            result.push_back(tmp);
            tmp.clear();
        }
        return result;    
    }
};

2.二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

参考解法：直接利用栈来完成，比较方便理解。

/**
 * 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) {}
 * };
 */

/*
二叉树的前序遍历是一种深度优先遍历方式,前序遍历的顺序是：
1.访问根节点。
2.前序遍历左子树。
3.前序遍历右子树。
下面的解法跟递归本质一样，不过是把栈给显示出来了。
*/
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
            stack<TreeNode*> TreeStack;
            vector<int> result;
            while(root != NULL || !(TreeStack.empty()))
            {
                while(root != NULL)
                {
                   result.push_back(root->val);
                   TreeStack.push(root);
                   root = root->left;         
                }
                root = TreeStack.top();
                TreeStack.pop();
                root = root->right;
            }
            return result;    
    }
};

3.二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

解法参考：

/**
 * 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:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> result;
        stack<TreeNode*> TreeStack;  //栈来辅助遍历
        while(root != NULL || !(TreeStack.empty()))  //确保了所有节点都会被访问到
        {
            while(root != NULL)  //内部循环用于遍历到最左边的节点，将遍历路径中的所有节点压入栈中
            {
                TreeStack.push(root);
                root = root->left;
            }
  //从栈中弹出一个节点，并将其值添加到结果向量中。这一步对应中序遍历中的“访问根节点”步骤。
            root = TreeStack.top();
            TreeStack.pop(); 
            result.push_back(root->val);
//转向当前节点的右子树，继续下一轮遍历
            root = root->right;
        }
        return result;    
    }
};

4.二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[3,2,1]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

  • 树中节点的数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

解法参考：

/**
 * 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:
        vector<int> postorderTraversal(TreeNode* root) 
        {
                vector<int> result;
                accessTree(result, root);
                return result;
        }
  
  //方法一递归，递归的话注意要传引用进去，否则对副本起作用后又消失了
        void accessTree(vector<int> &res, TreeNode* node)  
        {
                if(node == NULL) return;
                accessTree(res, node->left);
                accessTree(res, node->right);
                res.push_back(node->val);
        }
};

//方法三
/* vector<int> postorderTraversal(TreeNode* root) 
    {
        vector<int> result;
        stack<TreeNode*> TreeStack;
        TreeNode* preroot = NULL;
        if(root == NULL )  return result;
        while(root != NULL || !(TreeStack.empty()) )
        {
            while(root != NULL)
            {
                TreeStack.push(root);
                root = root->left;
            }
/*弹出一个，当其是否有右节点或右节点已经访问过，则可以访问这个结点，注意访问完后要把preroot置为它，然后结点置为null；如果不满足的话，则把这个结点压栈，然后变成它的右节点，再次进入上次的循环*/
/* 			root = TreeStack.top(); 
            TreeStack.pop();    
            if(root->right == NULL || root->right == preroot)
            {
               result.push_back(root->val);
               preroot = root ;
               root = NULL;     
            }else
            {
                TreeStack.push(root);
                root = root->right;
            }
        }
        return result;
    }
*/

5.二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

提示：

  • 树中节点的数量在 [0, 104] 区间内。
  • -100 <= Node.val <= 100

解法参考：

/**
 * 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) {}
 * };
 */
/*方法
一：直接递归来实现，每次往左和右递归然后取那个大的，最后加一
二：配合队列来实现，每次进队列的是同一层的结点，每次处理完一批结点，让深度加1
*/

//方法二
class Solution {
public:    
    int maxDepth(TreeNode* root)
    {
        int depth = 0;
        int size = 0;  //每次队列中的个数，即该层节点数
        queue<TreeNode*> T;
        if(root == NULL) return 0;
        T.push(root);
        while(!T.empty())
        {
            size = T.size();
            while(size)
            {
            root = T.front();
            T.pop();
            if(root->left != NULL)
            {
                T.push(root->left);
            }
            if(root->right != NULL)
            {
                T.push(root->right);
            }            
            --size;    
            }
            ++depth;
        }
        return depth;
    }
        
};    
    
//方法一递归
/*    int maxDepth(TreeNode* root) 
    {
        if(root == NULL)  return 0;
        else return max(maxDepth(root->left),maxDepth(root->right))+1;    
    }
*/

6.对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

  • 树中节点数目在范围 [1, 1000] 内
  • -100 <= Node.val <= 100

解法参考：

/**
 * 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) 
            {
               if(root == NULL) return true;      
               return access(root->left,root->right); 
            }

        bool access(TreeNode* l,TreeNode* r)
        {
              if(l == NULL && r == NULL)  return true;  

              if(l == NULL || r == NULL)  return false;
              if(l->val != r->val) return false;

              return access(l->left,r->right) && access(l->right,r->left);  
        }

};

//方法二
/*class Solution {
public:bool isSymmetric(TreeNode* root) 
    {
        //从根节点的左右开始
        TreeNode* u = root->left;
        TreeNode* v = root->right;
        //来个边界判断   不成立的话就开始双双进队列了
        if(root == NULL || (u == NULL && v == NULL))  return true;
        queue<TreeNode*> T;
        T.push(u);
        T.push(v);

        while(!T.empty())    //循环的存放
        {
          u = T.front();
          T.pop();
          v = T.front();
          T.pop();
          /*判断条件要注意判断是否都为空，如果是返回跳出本次循环 再弹两个出来 如果一半为空或者不相等则返回false 都不会则继续进队列     全部循环结束返回真*/
/*          if( u == NULL && v == NULL) continue;   //注意不是用break          
          if( (u == NULL || v == NULL) || u->val != v->val )  return false;  

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

          T.push(u->right);
          T.push(v->left);            
        }
        return true;
    }
};
*/

7.平衡二叉树

给定一个二叉树，判断它是否是 平衡二叉树

平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

  • 树中的节点数在范围 [0, 5000] 内
  • -104 <= Node.val <= 104

解法参考：

/**
 * 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) {}
 * };
 */


 /*方法
 一：自底向上递归解决，主要要想明白递归三要素，终止条件，处理过程，返回的值。 终止条件是root==null，处理过程是看高度差是否大于1，是的话返回负一。
二：自顶向下递归解决，好处是容易理解，坏处是重复调用，复杂度高 
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) 
    {
        if(root == NULL) return true;
        else
        { return abs(depth(root->left)-depth(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
        } 
    }
    
    int depth(TreeNode* root)
    {
        if(root == NULL) return 0;
        else return max(depth(root->left),depth(root->right))+1;    
    }

};

//自底向上递归
/*class Solution {
public:
    bool isBalanced(TreeNode* root) 
    {
        if(root == NULL) return true;
        return helper(root) != -1;
    }

    int helper(TreeNode* root)
    {
        if(root == NULL) return 0;

        int left = helper(root->left);
        int right = helper(root->right);

        if( left == -1 || right == -1 || abs(left-right)>1 )
        {
            return -1;
        }
        return max(left,right)+1;
    }
};
*/

8.翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

提示：

  • 树中节点数目范围在 [0, 100] 内
  • -100 <= Node.val <= 100

解法参考：

/**
 * 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 == NULL) return root;
        stack<TreeNode*> T;
        TreeNode* result = root;
        T.push(root);
        int size = 0;
        while(!T.empty())
        {
            size = T.size();
            while(size)
            {
            root = T.top();
            T.pop();

            TreeNode* tmp = root->left;
            root->left = root->right;
            root->right = tmp;

            if(root->left != NULL)
            {
                T.push(root->left);
            }
            if(root->right != NULL)
            {
                T.push(root->right);
            }
            --size;
            }
        }
        return result;
    }
};

//直接递归
/*class Solution {
public:
    TreeNode* invertTree(TreeNode* root) 
    {
        if(root == NULL) return root;
        invertTree(root->left);
        invertTree(root->right);

        TreeNode* tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        return root;
    }
};
*/

#23届找工作求助阵地##二叉树##笔面试##嵌入式##嵌入式软件实习#
嵌入式软件校招笔面试题汇总 文章被收录于专栏

该专栏是我整理的一些嵌入式软件笔面试常见的题目，在有一定计算机基础上，再过一遍该专栏的内容，对应届生校招来说基本上笔面试就没什么问题了！ 有任何疑问可随时与我联系，一起交流一起进步。

全部评论
觉得有用的帮楼主点个赞吧！ 感谢大家 ！！！
点赞 回复 分享
发布于 06-01 17:01 广东

相关推荐

昨天 08:22
合肥工业大学 Web前端
点赞 评论 收藏
分享
11-19 17:39
淘天集团_HR
淘天补录——算法类
是真没想到算法还要补人，之前T计划已经招了一批，加上陆续发放的offer，可能前面毁约的人还是有一部分，牛客随缘再捞点大佬，各位还没签约或者签了的捞们看看这里，流程处理绝对快（别让我求你投了）岗位算法技术未来生活实验室：算法工程师-机器学习、算法工程师-自然语言处理、算法工程师-多模态部门淘天集团算法技术未来生活实验室建议：熟悉LLM或MLLM的训练等技术，或者有相关领域的研究;在ICCV、CVPR等国际顶级会议、期刊上发表论文，或在相关学术会议组织的权威比赛中获奖或在校园内或互联网公司有相关实习或项目经历更佳;以及熟悉算法和infra的多面手们可以用我的内推链接（点击就是直接内推了）...
投递淘天集团等公司10个岗位 >
点赞 评论 收藏
分享
10-03 22:04
西南大学 Web前端
点赞 评论 收藏
分享
头像
11-24 10:06
中南大学 Java
点赞 评论 收藏
分享
5 5 评论
分享

招聘动态

查看更多

字节跳动

2025校园招聘

阿里云管培生

2025届校园招聘

快手Star

2025届招聘

快手

销售类投递专区

全站热榜

正在热议
# 25届秋招总结 #
303193次浏览 2692人参与
# 如果不工作真的会快乐吗 #
59474次浏览 519人参与
# 百度开奖 #
163934次浏览 981人参与
# 地方国企笔面经互助 #
3897次浏览 11人参与
# 美团求职进展汇总 #
1328226次浏览 12453人参与
# 选完offer后，你后悔学本专业吗 #
20170次浏览 144人参与
# 阿里云管培生offer #
17834次浏览 297人参与
# 正在实习的你，几点下班 #
52125次浏览 391人参与
# 国央企薪资爆料 #
8658次浏览 69人参与
# 如何一边实习一边秋招 #
992564次浏览 12640人参与
# 提前批简历挂麻了怎么办 #
146581次浏览 1948人参与
# 学历or实习经历，哪个更重要 #
51300次浏览 402人参与
# 海康威视求职进展汇总 #
399093次浏览 3406人参与
# 米哈游求职进展汇总 #
176133次浏览 1458人参与
# 求职遇到的搞笑事件 #
70904次浏览 577人参与
# 投递实习岗位前的准备 #
1179804次浏览 18397人参与
# 面试体验感最好的是哪家？ #
85168次浏览 846人参与
# 实习生应该准时下班吗 #
167497次浏览 1159人参与
# 得物求职进展汇总 #
66374次浏览 682人参与
# 网申一定要掌握的小技巧 #
5354次浏览 53人参与
# 招聘要求与实际实习内容不符怎么办 #
10315次浏览 273人参与
# 0offer是寒冬太冷还是我太菜 #
899001次浏览 8015人参与
牛客网
牛客企业服务