面试算法题之二叉树|小试牛刀

🍄前言

大家好哇，我是一勺黑猫。作为一名计算机大三学生，马上就到找实习的时候了。最近陆续在做一些算法题，拿来和大家分享一下~

🍄二叉树

我们知道，二叉树也就是只有两个孩子节点的树。二叉树涉及到很多题目，比较容易理解的题目有遍历二叉树（前序中序后序）、二叉树的深度（dfs搜索）等等。
今天我们来说一说二叉树的深度。如果根节点不为空，那这个树的深度就是1+max(左子树深度, 右子树深度)，如下图：

二叉树如果是由链表形式给出的，我们通常构造这样的结构体：

struct TreeNode{
    int val;
    TreeNode *left,*right;
};

可以很容易写出二叉树深度递归的代码：

int dfs(TreeNode *root){
    if(root==NULL)
        return 0;
    return 1+max(dfs(root->left),dfs(root->right));
}

下面给大家看一道具体的题目：

🌰解题思路：

本题的输入形式，每个节点的序号可以和数组下标一一对应，并不需要创建链表，只需存储左右子树的序号，这样left域和right域的类型用int就可以了。具体代码如下。

🌰AC代码：

#include<iostream>
#include<vector>
using namespace std;

struct TreeNode{
    int left,right;
};

vector<TreeNode> v;    //存储二叉树的每个节点

int dfs(int root){

    //根节点为0时说明是空节点，深度为0
    if(root==0)
        return 0;

    //返回根节点的深度1+左右子树的最大深度
    return 1+max(dfs(v[root].left),dfs(v[root].right));
}

int main(){
    int n;
    cin>>n;
    v.resize(n+1);
    for(int i=1;i<=n;i++)
        cin>>v[i].left>>v[i].right;
    cout<<dfs(1);
    return 0;
}

🍄小试牛刀

感觉没有练够的小伙伴可以在我们的牛客网上继续做题哦，我为大家找到一些同类型题目，难度由易到难，可以尝试一下~

• 对称的二叉树_牛客题霸_牛客网
• 二叉树的镜像_牛客题霸_牛客网
• 二叉搜索树的最近公共祖先_牛客题霸_牛客网
• 判断是不是完全二叉树_牛客题霸_牛客网
• 在二叉树中找到两个节点的最近公共祖先_牛客题霸_牛客网

后续会推出同系列文章，感兴趣的小伙伴三连支持一下！！感谢大家