目录

• 题目：随机节点
• 一、思路
• 二、解法
• • 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);
        }
    }
};