地鼠安家问题，二叉树求助大佬。

Question

d 是一个公认的美丽校园。一天，fd 来了一群地鼠,编号为 1 到 n，他们希望 在这里定居。现在先由第一只地鼠往下打一个单位的距离，并且在那里安家。对 于每一个已经安家的地鼠，如果他左下或右下没有邻居，那还没安家的地鼠就可 以在他的左下或者右下安家。地鼠们已经建完所有的窝了，他们评价这些窝合格 的标准是它们能不能形成一棵二叉搜索树。现在需要你帮助他们评估一下他们的 窝挖的是否合格。

★数据输入

第 1 行一个整数 n，表示地鼠总共 n 只。接下来一共 n 行，每一行三个数：l,o,r，其中 l 表示编号为 o 的地鼠的左邻居的编号，r 表示的是编号为 o 的右邻居的编号，如果没有左 邻居或右邻居，则 l 或 r 为-1。1<=n<=10000。

★数据输出

输出一行，如果如果他们的窝合格，则输出安居在最深的窝的地鼠离地面的距离，如果不合格，则输出-1。

输入示例
5
-1 1 -1
1 2 3
-1 3 -1
2 4 5
-1 5 -1
输出示例
3

Answer 1

1.构建二叉树，通过parent判断是否为根节点；
2.判断是否是二叉搜索树；
3.求树高；

#include <iostream>
#include <vector>

using namespace std;

struct TreeNode
{
    TreeNode* left;
    TreeNode* right;
    TreeNode* paraent;
    int _val;
    TreeNode(int val)
        :_val(val), left(NULL), right(NULL), paraent(NULL){}
};

// 判断root是否是搜索二叉树
// 中序遍历时，前一个遍历的节点肯定小于当前遍历的节点
TreeNode* pre = NULL;
bool issearchTree(TreeNode* root)
{
    if (root == NULL)   return true;

    bool left = issearchTree(root->left);
    if (pre != NULL && pre->_val > root->_val)
    {
        return false;
    }
    pre = root;
    bool right = issearchTree(root->right);

    return left && right;
}

// 求二叉树的高度
int getHeight(TreeNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    int left = getHeight(root->left);
    int right = getHeight(root->right);
    return ((left > right)? left : right) + 1;
}

int main()
{
    int n = 0;

    cin >> n;
    vector<TreeNode*> vec(n + 1);
    for (int i = 1; i <= n; i++)
    {
        TreeNode* node = new TreeNode(i);
        vec[i] = node;
    }

    // 通过输入建树
    for (int i = 1; i <= n; i++)
    {
        int l, o, r;
        cin >> l >> o >> r;
        if (l != -1)
        {
            vec[o]->left = vec[l];
            vec[l]->paraent = vec[o];
        }
        if (r != -1)
        {
            vec[o]->right = vec[r];
            vec[r]->paraent = vec[o];
        }
    }

    // 遍历查找根节点
    TreeNode* root = NULL;
    for (int i = 1; i <= n; i++)
    {
        if (vec[i]->paraent == NULL)
        {
            root = vec[i];
        }
    }

    if (issearchTree(root) == true)
    {
        cout << getHeight(root) << endl;
    }
    else
    {
        cout << -1 << endl;
    }
    return 0;
}