HH_Knight
2020-10-15 11:48
采纳率: 50%
浏览 75

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

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

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • JustNow_Man 2020-10-15 15:43
    已采纳

    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;
    }
    
    打赏 评论

相关推荐 更多相似问题