文档章节

网易实习生真题(二叉树)

r
 ranjiewen
发布于 2016/11/03 23:52
字数 611
阅读 2
收藏 0

    2016.3月的网易实习生机试题,考察了的对二叉树的灵活应用,理解中序遍历的用处!可能还有优化的解,大家自由发挥!

//有一棵二叉树,树上每个点标有权值,权值各不相同,请设计一个算法算出权值最大的叶节点到权值最小的叶节点的距离。
//二叉树每条边的距离为1,一个节点经过多少条边到达另一个节点为这两个节点之间的距离。
//给定二叉树的根节点root,请返回所求距离。


#include<iostream>
using namespace std;
#include<vector>
struct TreeNode {

    int val;

    struct TreeNode *left;

    struct TreeNode *right;

    TreeNode(int x) :

        val(x), left(nullptr), right(nullptr) {
    }
};


//1注意点 权值最大的叶子节点到权值最小的叶子节点,不是所有的节点,是叶子结点
//2.用俩个变量标记俩个节点的位置,求出根节点到他们的路径,如果有重复的路径就减去重复的路径的长度.

class Tree {
    void Inorder(TreeNode *root, vector<int>&v, int &small, int &big){
        //中序遍历获得最小的叶节点和最大的叶节点的索引
        if (!root)
            return;
        Inorder(root->left, v, small, big);
        v.push_back(root->val);
        if (root->left == NULL&&root->right == NULL){    //叶子节点   //跟着遍历的过程走,第一个叶子结点,samll=big,v里面加值,
            if (small == -1 || big == -1)
                small = big = (int)v.size() - 1;
            else{                                                    //第二个叶子结点,samll=big!=-1,v里面有第一个节点到到第二个叶子结点的路径值,比较改变samll和big的值
                if (root->val<v[small]) small = (int)v.size() - 1;
                if (root->val>v[big])   big = (int)v.size() - 1;
            }
        }
        Inorder(root->right, v, small, big);
    }
public:
    int getDis(TreeNode* root) {
        int small = -1, big = -1;
        vector<int>v;
        Inorder(root, v, small, big);  //v里面为中序遍历的节点值
        TreeNode * p = root;
        vector<int>v1, v2;
        int pos;
        while (true) {    //寻找路径
            pos = (int)(find(v.begin(), v.end(), p->val) - v.begin());//找到根节点的索引
            v1.push_back(v[pos]);  //存储的是根节点到最小目标节点的路径值
            if (small>pos)         //索引比较
                p = p->right;
            else if (small<pos)
                p = p->left;
            else
                break;
        }
        p = root;
        while (true) {
            pos = (int)(find(v.begin(), v.end(), p->val) - v.begin());
            v2.push_back(v[pos]);
            if (big>pos)
                p = p->right;
            else if (big<pos)
                p = p->left;
            else
                break;
        }
        int i, j;
        for (i = 0, j = 0; j<v2.size() - 1 && i<v1.size() - 1; ++i, ++j) {   //去重
            if (!(v1[i] == v2[j] && v1[i + 1] == v2[j + 1]))
                break;
        }
        return (int)v1.size() - 1 + (int)v2.size() - 1 - 2 * i;  //i为前面有几个相同的
    }
};

 

本文转载自:http://www.cnblogs.com/ranjiewen/p/5341287.html

r
粉丝 1
博文 203
码字总数 28
作品 0
武汉
程序员
私信 提问
90 道名企笔试和算法题 (含答题讨论)

(点击上方公众号,可快速关注) 节选自「算法爱好者」微信公号的精选算法题和名企笔试题。 问:如何获取题目列表? 答:① 长摁二维码关注「算法爱好者」,② 然后给它发送 名企笔试 或 算法...

Python开发者
2018/01/21
0
0
网易java实习生面试10个问题,你会几个?

此前,w3cschool app分享了阿里巴巴java面经、小米java面经、网易java面经。 近日,我们在w3cschool app开发者头条上,可以看到网易java实习生面经。 在分享网易java实习生面经之前,我们还是...

W3Cschool
2017/12/05
0
0
网申 网易游戏 测试开发 一面凉经

约的我4点钟面试,提前大概10分钟打了过来。 (1)自我介绍 (2)玩过什么游戏 直接说Dota2。问我多少分,我说4000分。对面:“噢,5年才打到4000分啊(????我对面这个是5000分大手子?)...

牛客网
2018/05/12
0
0
(已拿offer)腾讯实习生笔试到面试总结(附带华为阿里面试经历)

导读:快到暑假了,有不少读者还是学生,想找一份实习,好的公司,只能说是好的起点,不能代表全部。公司强大,不代表个人一定强大,小公司同样也有大牛,不羡慕,不虚浮,脚踏实地,今天,分...

我最喜欢三大框架
06/12
11
0
别再翻了,面试二叉树看着 11 个就够了~

写在前边 数据结构与算法: 不知道你有没有这种困惑,虽然刷了很多算法题,当我去面试的时候,面试官让你手写一个算法,可能你对此算法很熟悉,知道实现思路,但是总是不知道该在什么地方写,...

一个不甘平凡的码农
09/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

哈希

第一个只出现一次的字符的位置

Garphy
24分钟前
4
0
Centos7.7之离线安装kubectl

Centos7.7,kubernates-1.13.5. 我的Centos7.7上已经安装了kubernates 1.13.5,但是没有kubectl命令,手动安装 浏览器中访问https://storage.googleapis.com/kubernetes-release/release/sta......

克虏伯
27分钟前
4
0
redis原理及应用

一、redis来源 二、数据类型 三、主流的应用场景 四、特性 五、补充 一、 redis来源 redis作者:Salvatore Sanfilippo (antirez),男,意大利人. 需求:一个访客信息追踪网站,网站可以通过...

天子剑毅
34分钟前
3
0
12_多线程

12_多线程 wait():一旦执行此方法,当前线程就进入阻塞状态,并释放同步监视器(释放锁)。 notify():一旦执行此方法,就会唤醒被wait的一个线程。如果有多个线程被wait,就唤醒优先级高的那个...

行者终成事
39分钟前
5
0
图片的切换功能

<!DOCTYPE html><html><head> <meta charset="UTF-8"> <title></title> <style type="text/css"> * { margin: 0; padding: 0; ......

zhengzhixiang
今天
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部