程序员面试金典 --- 4.11随机节点

2021/11/10 17:10:50

本文主要是介绍程序员面试金典 --- 4.11随机节点,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

  • 题目:随机节点
  • 一、思路
  • 二、解法
    • 1.选项3
    • 2.选项4


题目:随机节点

你现在要从头开始实现一个二叉树类,该类除了插入(insert)、查找 (find)和删除(delete)方法外,需要实现 getRandomNode()方法用于返回树中的任意节点。该方法应该以相同的概率选择任意的节点。设计并实现 getRandomNode 方法并解释如何实现其
他方法。


一、思路

需要注意到此题使用了一种十分有趣的描述方式:面试官并不是简单地说:“请设计一个算法,从二叉树中返回一个随机节点。”此题要求我们从零开始实现一个类。此题如此描述并没有根据,我们或许需要访问数据结构的部分内部元素。

  • 选项1(可行但是运行较慢)
    • 树中的节点复制到数组中 进行随机 用时O(N) 空间O(N) 方法过于简单
  • 选项2(可行但是运行较慢)
    • 维护一个数组 使数组节点于树中节点相同 这样虽然添加和获取随机节点用时为O(1)但是删除时 从数组中删除复杂度为O(N)
  • 选项3(可行但是运行较快)
    • 每个节点都记住左右子树的节点数 然后进行按个数的随机
  • 选项4(可行但是运行较快)
    • 按照选项3的思路 但是只随机一次X1,当随机子树之前用X1-(leftSize+1)

二、解法

1.选项3

class TreeNode{
public:
    int data;
    TreeNode *left;
    TreeNode *right;
    int size = 0;
    TreeNode(int d){
        data = d;
        size = 1;
        left = NULL;
        right = NULL;
    }
    void insertInOrder(int d){
        if(d <= data){
            if(left == NULL){
                left = new TreeNode(d);
            }else{
                left->insertInOrder(d);
            }
        }else {
            if(right == NULL){
                right = new TreeNode(d);
            }else{
                right->insertInOrder(d);
            }
        }
        size++;
    }
    TreeNode* find(int d){
        if(d == data){
            return this;
        }else if(d < data){
            return left != NULL ? left->find(d) : NULL;
        }else if(d > data){
            return right != NULL ? right->find(d) : NULL;
        }
    }
    TreeNode* getRandomNode(){
        int leftSize = left == NULL ? 0 : left->size;
        int index = rand() % size;
        if(index < leftSize){
            return left->getRandomNode();
        }else if(index == leftSize){
            return this;
        }else{
            return right->getRandomNode();
        }
    }
};

2.选项4

class TreeNode{
public:
    int data;
    TreeNode *left;
    TreeNode *right;
    int size = 0;
    TreeNode(int d){
        data = d;
        size = 1;
        left = NULL;
        right = NULL;
    }
    TreeNode* getIthNode(int i){
        int leftSize = left == NULL ? 0 : left->size;
        if(i < leftSize){
            return left->getIthNode(i);
        }else if(i == leftSize){
            return this;
        }else{
            return right->getIthNode(i-(leftSize + 1));
        }
    }
    void insertInOrder(int d){
        if(d <= data){
            if(left == NULL){
                left = new TreeNode(d);
            }else{
                left->insertInOrder(d);
            }
        }else {
            if(right == NULL){
                right = new TreeNode(d);
            }else{
                right->insertInOrder(d);
            }
        }
        size++;
    }
    TreeNode* find(int d){
        if(d == data){
            return this;
        }else if(d < data){
            return left != NULL ? left->find(d) : NULL;
        }else if(d > data){
            return right != NULL ? right->find(d) : NULL;
        }
    }
};

class Tree{
public:
    TreeNode *root = NULL;
    int size(){return root == NULL ? 0 : root->size;}
    TreeNode *getRandomNode(){
        if(root == NULL) return NULL;
        int i = rand() % size();
        return root->getIthNode(i);
    }
    void insertInOrder(int value){
        if(root == NULL){
            root = new TreeNode(value);
        }else{
            root->insertInOrder(value);
        }
    }
};


这篇关于程序员面试金典 --- 4.11随机节点的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程