嵌入式软件常用面试题汇总之 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届找工作求助阵地##二叉树##笔面试##嵌入式##嵌入式软件实习#
嵌入式软件校招笔面试题汇总 文章被收录于专栏

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

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

相关推荐

10-29 19:30
门头沟学院 后端工程师
点赞 评论 收藏
分享
10-30 19:20
门头沟学院 前端工程师
点赞 评论 收藏
分享
10-10 15:23
陕西师范大学 Java
点赞 评论 收藏
分享
10-10 10:02
武汉晴川学院 C++
点赞 评论 收藏
分享
10-31 14:34
门头沟学院 游戏后端
点赞 评论 收藏
分享
评论
5
5
分享

招聘动态

查看更多

字节跳动火山引擎

2026校园招聘

厦门银行

2026届秋季校园招聘

联想

2026届校园招聘

字节跳动

2026校园招聘

联想

26届AI专项｜内推码NK2026

快手

2026届校园招聘

中欧基金

2026届卓越之星校招

联想

2026届校园招聘

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 今年秋招是回暖还是遇冷 #
10591次浏览 67人参与
# 实习教会我的事 #
35944次浏览 313人参与
# 京东开奖 #
439049次浏览 2483人参与
# 我来点评面试官 #
4483次浏览 36人参与
# 如果不考虑收入，你最想做什么工作？ #
35603次浏览 211人参与
# 你实习是赚钱了还是亏钱了？ #
12210次浏览 114人参与
# 商战，最累的是我们 #
24232次浏览 89人参与
# 用一句话形容你的团队氛围 #
7458次浏览 104人参与
# 京东工作体验 #
16667次浏览 96人参与
# 秋招开始捡漏了吗 #
47209次浏览 329人参与
# 同bg的你秋招战况如何？ #
162653次浏览 945人参与
# 找工作八股要背到什么程度？ #
7212次浏览 118人参与
# 考研人，我有话说 #
150070次浏览 1198人参与
# 你找工作是从容有余 or 匆忙滚爬？ #
4805次浏览 54人参与
# 上班后，才发现大学__白学了 #
7893次浏览 51人参与
# 硬件人，你被哪些公司给挂了 #
68619次浏览 932人参与
# 三一重工求职进展汇总 #
21276次浏览 82人参与
# 58同城求职进展汇总 #
38546次浏览 260人参与
# 机械人，你的第一份感谢信是谁给的 #
37854次浏览 346人参与
# 今年秋招还有金九银十吗 #
30275次浏览 275人参与
# 大学生该如何认清当下的就业环境？ #
107392次浏览 635人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务