关键词：
数据结构面试题及答案讲解：二叉树专题（上）
本节目标
-
1、求二叉树的最大深度。（2018年腾讯面试题）
-
2、判断一个二叉树是否是高度平衡的二叉树。（2020年字节跳动面试真题）
-
3、根据一棵树的前序遍历与中序遍历构造二叉树（Leetcode105题）
1、求二叉树的最大深度。
OJ链接：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/submissions/
高频考察的大厂云图：
解题思路：
当前树的深度 = max(左子树深度，右子树深度)+1，所以要求当前树的深度得先递归求出左子树深度和右子树深度。要求出左右子树的深度同样的道理，再往下递归，直到遇到空树，深度直接返回0。
代码实现：
/**
* 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:
int maxDepth(TreeNode* root)
if(root == NULL)
return 0;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return leftDepth > rightDepth ? leftDepth+1 : rightDepth+1;
;2、判断一个二叉树是否是高度平衡的二叉树
高频考察的大厂云图：
解题思路：
什么是高度平衡二叉树？一颗二叉树的左右子树的高度差不超过1，且树中的所有子树都满足这个条件，则称这颗二叉树是高度平衡二叉树。
那么要判断一颗二叉树是否是平衡二叉树可以分为3步：
- 求出当前树的左右子树的高度，判断是否满足高度差<=1. 满足则继续第2点
- 按第一点的方式，递归检查判断左子树. 满足则继续第3点
- 按第一点的方式，递归检查判断右子树. 满足则是高度平衡二叉树
代码实现：
/**
* 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:
int maxDepth(TreeNode* root)
if(root == NULL)
return 0;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return leftDepth > rightDepth ? leftDepth+1 : rightDepth+1;
bool isBalanced(TreeNode* root)
if(root == NULL)
return true;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return abs(leftDepth-rightDepth) < 2
&& isBalanced(root->left)
&& isBalanced(root->right);
;3、根据一棵树的前序遍历与中序遍历构造二叉树。
OJ链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
高频考察的大厂云图：
解题思路：
- 前序的顺序为：根、左子树、右子树 中序的顺序为：左子树、根、右子树
- 根据前序可以确立前序构建树的每个树的根节点，创建根，再用根节点把中序分割出左子树和右子树的区间，再递归创建坐子树和右子树
- 当子树区间为没有数据时，递归返回空。
代码实现：
/**
* 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:
TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& prei, int inbegin, int inend)
if(inbegin > inend) return nullptr;
int rootVal = preorder[prei];
TreeNode* root = new TreeNode(rootVal);
// 在中序序列中去找root的位置
int inRooti = inbegin;
while(inRooti <= inend)
if(inorder[inRooti] == rootVal)
break;
else
++inRooti;
// [inbegin, inRooti-1] inRooti [inRooti+1, inend] 左子树的中序[inbegin, inRooti-1] 右子树的中序[inRooti+1, inend]
// 如果中序左区间存在则递归创建左子树，如果中序左区间不存在，则左子树是空树
if(inbegin <= inRooti-1)
root->left = _buildTree(preorder, inorder, ++prei, inbegin, inRooti-1);
else
root->left= nullptr;
// 同上
if(inRooti+1 <= inend)
root->right = _buildTree(preorder, inorder, ++prei, inRooti+1, inend);
else
root->right = nullptr;
return root;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
int prei = 0;
int inbegin = 0;
int inend = inorder.size()-1;
return _buildTree(preorder, inorder, prei, inbegin, inend);
;如果你有不是很明白的地方，这里有讲解视频哦：
击链接观看：单击链接就可以了
数据结构面试题及答案解析系列如果对你有帮助，请点赞，转发，鼓励博主继续更新下去哦
上一篇：https://blog.csdn.net/bitzhidu/article/details/106474004
21年最新python面试题及答案汇总详解(上)(代码片段)
Python面试你做准备了吗？下面小千整理了一套2021年最新Python常见面试题目，及Python面试题目答案汇总。希望能够帮助到大家。21年最新Python面试题及答案汇总详解(上)1、列表(list)和元组(tuple)有什么区别？在我每一次... 查看详情
二叉树相关面试题数据结构(代码片段)
题目目录基础面试题二叉树的前序遍历二叉树的中序遍历二叉树的后续遍历结果相同的树另一棵树的子树二叉树的最大深度平衡二叉树判断对称二叉树进阶面试题二叉树的遍历及构建二叉树的分层遍历二叉树的最近公共祖先二叉... 查看详情
数据结构二叉树相关面试题java版leetcode题-------二叉树(代码片段)
文章目录基础面试题第一题:二叉树的前序遍历。(递归解法)(迭代解法)第二题:二叉树的中序遍历。(递归解法)(迭代解法)第三题:二叉树的后序遍历。(递归解法)(迭代解法)第四题:相同的树解题思路:代码实现:第五题:另一棵树的子... 查看详情
python数据结构系列☀️《树与二叉树-基础知识》——知识点讲解+代码实现☀️(代码片段)
文章目录数据结构之树和二叉树第一部分树和二叉树的基础知识1、树和二叉树的定义1.1树的定义1.2树的基本术语1.3二叉树的定义2、二叉树的性质和存储结构2.1二叉树的性质2.2二叉树的存储结构2.2.1顺序存储2.2.2链式存储2.3遍历二... 查看详情
代码面试需要知道的8种数据结构(附面试题及答案链接)
译者按：搞定面试，不要急着刷题，先弄懂什么是数据结构！原文：Thetopdatastructuresyoushouldknowforyournextcodinginterview译者：Fundebug为了保证可读性，本文采用意译而非直译。另外，本文版权归原作者所有，翻译仅用于学习。1976年，... 查看详情
代码面试需要知道的8种数据结构(附面试题及答案链接)
...学家写一本书《Algorithms+DataStructures=Programs》。即：算法+数据结构=程序。40多年过去了，这个 查看详情
[算法]死磕二叉树专题算法(代码片段)
1. 二叉树遍历（递归和非递归）构造二叉树：classNodepublicStringvalue;publicNodeleft;publicNoderight;publicNode(Stringvalue)this.value=value;递归版前序遍历：publicstaticvoidpreOrder(Nodehead)if(head!=null)System.out.pr 查看详情
史上最全redis面试题及答案
1、什么是Redis？2、Redis相比memcached有哪些优势？3、Redis支持哪几种数据类型？4、Redis主要消耗什么物理资源？5、Redis的全称是什么？6、Redis有哪几种数据淘汰策略？7、Redis官方为什么不提供Windows版本？8、一个字符串类型的值能... 查看详情
[专题五]二叉树(代码片段)
树结构专题二叉树几种典型运算typedefstructBTNodeintdata;structBTNode*left;structBTNode*right;BTNode;//创建二叉树BTNodeBinaryTree()BTNode*T=(BTNode*)malloc(sizeof(BTNode));T->data=0;returnT;//BinaryEmpty(T):bool判断树是否为空//Root(T):int返回根结点data//构造二叉... 查看详情
2020java程序员18个大厂的面试真题流出，熟悉这些拿offer率90%
...扫描二维码即可免费领取！这些资料包括一下这一系列。面试专题：01.Java语法基础_面试专题及答案.pdf 02.Java集合面试专题及答案.pdf 03.并发编程面试专题及答案(上).pdf04.并发编程面试专题及答案(下).pdf&... 查看详情
杠上数据结构-二叉树(代码片段)
二叉树在面试过程中出现的频率非常高，因此熟练掌握二叉树是吊打面试官的必备技能。基本认识二叉树：是节点的一个有限集合，该集合要么为空，要么由一个根节点加上左子树和右子树组成。特点：每个... 查看详情
面试---算法面试(代码片段)
算法二叉树二叉树的遍历(前序、中序、后序、层序)递归版本非递归版本二叉树的常见oj二叉树的右视图N叉树的层序遍历反转二叉树对称二叉树子树问题二叉树的最近祖先问题二叉树的最大高度问题二叉树的最小深度完全二叉树... 查看详情
java面试题及答案2020java最新面试题及答案2020一(代码片段)
java最新面试题及答案20201.一个".java"源文件中是否可以包括多个类（不是内部类）？有什么限制？一个“.java”源文件里面可以包含多个类，但是只允许有一java最新面试题及答案个public类，并且类名必须和文件名一致。每... 查看详情
java面试题及答案2020_java面试题答案1(代码片段)
java面试题及答案2020持续更新。。本文收集了一些经典的Java面试题及其答案1、面向对象的特征有哪些方面？答：面向对象的特征主要有以下几个方面：抽象：抽象是将一类对象的共同特征总结出来构造类的过程，包括数据抽象... 查看详情
微软面试题：leetcode543.二叉树的直径出现次数：3(代码片段)
题目描述： 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。分析： 本题和 124.二叉树中的最大路径和 是一样的... 查看详情
redis面试题及答案整理
1、什么是Redis？简述它的优缺点？Redis的全称是：RemoteDictionary.Server，本质上是一个Key-Value类型的内存数据库，很像memcached，整个数据库统统加载在内存当中进行操作，定期通过异步操作把数据库数据flush到硬盘上进行保存。因为... 查看详情
二叉树专题(代码片段)
二叉树中序非递归从root开始，一直往左孩子走入栈，走到头倒退回去到有右孩子的点重复上一个步骤，注意，这中间经过的栈扔出去的点，包括最后一个有右孩子的点都要存到ans里面注意判断stack为空/***Definitionforabinarytreenode.*st... 查看详情
排序二叉树，平衡二叉树和红黑树的概念以及相关的操作讲解
1.排序二叉树 排序二叉树是一种特殊结构的二叉树，可以非常方便地对树中所有节点进行排序和检索。排序二叉树要么是一棵空二叉树，要么是具有下列性质的二叉树：若它的左子树不空，则左子树上所有节点的值均小... 查看详情