输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [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;
}
};
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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);
}
};
