【题解】树上最强节点

题意

通过一个数组构建一个棵二叉排序树，二叉树上的每一个节点都可以看作树的根，求其最大深度是多少。

题解

首先是建树，由于二叉排序树性质，有可能会退化成链，所以我们不能以数组的形式来构建二叉树。所以要用结构体来实现。

struct Tree
{
    int v;
    Tree *lchild;
    Tree *rchild;
};

用递归的形式来构造这棵树

void Insert(Tree *&T,int v)
{
    if(T==NULL)
    {
        T=new Tree;
        T->lchild=NULL;
        T->rchild=NULL;
        T->v=v;
    }
    else if(T->v>v)
        Insert(T->lchild,v);
    else
        Insert(T->rchild,v);
}

构建完之后，是如何找到题意中所说的以某个节点为根数的最大深度。实际上问题转换一下就变成了求解该二叉树的直径。二叉树的直径可以看作是某一子树左右子树深度之和中的最大值。所以我们在求整棵树的时候可以用一个全局变量来记录左右子树深度之和的最大值。最后输出该值就可以了。

复杂度

时间复杂度为
空间复杂度为

代码

struct Tree
{
    int v;
    Tree *lchild;
    Tree *rchild;
};
void Insert(Tree *&T,int v)
{
    if(T==NULL)
    {
        T=new Tree;
        T->lchild=NULL;
        T->rchild=NULL;
        T->v=v;
    }
    else if(T->v>v)
        Insert(T->lchild,v);
    else
        Insert(T->rchild,v);
}
int maxn=0;
int Deep(Tree *T)
{
    if(T==NULL)
        return 0;
    int left=Deep(T->lchild);
    int right=Deep(T->rchild);
    maxn=max(maxn,left+right)+1;
    return max(left,right)+1;
}
class Solution {
public:
    /**
     * 
     * @param a int整型vector 
     * @return int整型
     */
    int bestNode(vector<int>& a) {
        // write code here
        Tree *T=NULL;
        for(int i=0;i<a.size();i++)
            Insert(T,a[i]);
        Deep(T);
        return maxn-2;
    }
};