剑指 Offer 55 - I. 二叉树的深度
输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。
例如:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
该题目比较简单,为二叉树基本类型的题目,二叉树一般都要用到递归来解决
首先我们能够想到,一个数如果root==nullptr,说明该数节点为0,如果root!=nullptr并且它的左右子树都为nullptr,说明该节点即为叶子节点,那么我们就能写出以下代码:
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root==nullptr)
{
return 0;
}
if(root->left==nullptr&&root->right==nullptr)
{
return 1;
}
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
};
剑指 Offer 07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uPXuguJj-1630925881571)(https://raw.githubusercontent.com/qingyan520/Cloud_img/master/img/image-20210904214225686.png)]
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
在一棵二叉树中,只要知道了前序遍历和中序遍历,或者中序遍历和后续遍历就能重建整科二叉树
代码:
//根据前序和中序或者中序和后续就能重建二叉树
class Solution {
public:
TreeNode*_bulidTree(vector<int>&preorder,int pre_start,int pre_end,vector<int>&inorder,int ind_start,int ind_end)
{
//递归终止的条件
if(pre_start>pre_end||ind_start>ind_end)
{
return nullptr;
}
//创建根结点
TreeNode*root=new TreeNode(preorder[pre_start]);
//在中序序列中找到根结点,将中序序列分成左右子树,前序序列往后数对应的左子树数量
for(int i=0;i<=ind_end;i++)
{
if(root->val==inorder[i])
{
root->left=_bulidTree(preorder,pre_start+1,pre_start+i-ind_start,inorder,ind_start,i-1);
root->right=_bulidTree(preorder,pre_start+i-ind_start+1,pre_end,inorder,i+1,ind_end);
}
}
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
//数据不正确,直接进行退出
if(preorder.empty()||inorder.empty()||preorder.size()!=inorder.size())
{
return nullptr;
}
return _bulidTree(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
}
};