字节跳动面试210615大数据java(搜索二叉树后续遍历,非递归)(代码片段)

史上最强的弟子 史上最强的弟子     2022-12-04     607

关键词:

 面试的是一位大数据组的老大,上来就让先写一个搜索二叉树后续遍历,半小时写出来。

因为当时太紧张没写出来后面捋了一下思路写出来了。这个其实很考虑思想的转变过程,和大家分享一下解法,经过检验100% 能输出,原创努力来之不易。继续努力。

package jieduaner;

import java.util.Arrays;
import java.util.List;

public class ErTreeFind 

    //给数组构成搜索二叉树 后续遍历,   搜索二叉树特点,1.根节点最多有两个子节点,2.根节点值大于左节点的值,根节点的值小于右节点的值。
    
    public static void main(String[] args) 
        //[123 576 4]
        /*     4
          2        6
        1   3    5    7
        */
        ErTreeFind erTreeFind = new ErTreeFind();
        Integer[] datas = new Integer[]1,3,2,5,7,6,4;
        List<Integer> dataList = Arrays.asList(datas);
        ErTreeNode erTreeNode = erTreeFind.getNode(null,dataList);
        System.out.println(erTreeNode);

        /*   1
                 2
                     3
                        4
                            5*/
        datas = new Integer[]5,4,3,2,1;
        dataList = Arrays.asList(datas);
        erTreeNode = erTreeFind.getNode(null,dataList);
        System.out.println(erTreeNode);
        /*                        5
                            4
                        3
                   2
                1 */
        datas = new Integer[]1,2,3,4,5;
        dataList = Arrays.asList(datas);
        erTreeNode = erTreeFind.getNode(null,dataList);
        System.out.println(erTreeNode);
    

    public ErTreeNode getNode(ErTreeNode erTreeNode,List<Integer> dataList)
        ErTreeNode returnNode = null;
        //边界
        if(dataList==null||dataList.size()== 0)
            return null;
        

        ErTreeNode rootNode = new ErTreeNode();
        rootNode.value = dataList.get(dataList.size()-1);
        List<Integer> subDataList = dataList.subList(0,dataList.size()-1);
        if(erTreeNode == null)
            returnNode = rootNode;
        
        if(erTreeNode!= null)
            if(erTreeNode.value>rootNode.value)
                erTreeNode.leftNode = rootNode;
            else
                erTreeNode.rightNode = rootNode;
            
        
        int remark = -1;
        for(int i = subDataList.size()-1;i>=0;i--)
            int value = subDataList.get(i);
            if(value<rootNode.value)
                remark = i;
                break;
            
        
        //右树
        getNode(rootNode,subDataList.subList(remark==-1?0:remark+1, subDataList.size()));
        //左树
        if(remark>=0) 
            getNode(rootNode, subDataList.subList(0, remark+1));
        
        return returnNode;
    




class ErTreeNode
    public ErTreeNode leftNode;
    public ErTreeNode rightNode;
    public Integer value;

    @Override
    public String toString() 
        return "ErTreeNode" +
                "leftNode=" + leftNode +
                ", rightNode=" + rightNode +
                ", value=" + value +
                '';
    

输出结果:

//测试1输出
ErTreeNodeleftNode=ErTreeNodeleftNode=ErTreeNodeleftNode=null, rightNode=null, value=1, rightNode=ErTreeNodeleftNode=null, rightNode=null, value=3, value=2, rightNode=ErTreeNodeleftNode=ErTreeNodeleftNode=null, rightNode=null, value=5, rightNode=ErTreeNodeleftNode=null, rightNode=null, value=7, value=6, value=4


//测试2输出
ErTreeNodeleftNode=null, rightNode=ErTreeNodeleftNode=null, rightNode=ErTreeNodeleftNode=null, rightNode=ErTreeNodeleftNode=null, rightNode=ErTreeNodeleftNode=null, rightNode=null, value=5, value=4, value=3, value=2, value=1


//测试3输出
ErTreeNodeleftNode=ErTreeNodeleftNode=ErTreeNodeleftNode=ErTreeNodeleftNode=ErTreeNodeleftNode=null, rightNode=null, value=1, rightNode=null, value=2, rightNode=null, value=3, rightNode=null, value=4, rightNode=null, value=5

字节跳动面试210615大数据java(搜索二叉树后续遍历,非递归)(代码片段)

 面试的是一位大数据组的老大,上来就让先写一个搜索二叉树后续遍历,半小时写出来。因为当时太紧张没写出来后面捋了一下思路写出来了。这个其实很考虑思想的转变过程,和大家分享一下解法,经过检验10... 查看详情

字节跳动面试笔试总结——算法岗位

目录1.一棵二叉树,求最大通路长度(即最大左右子树高度之和)  查看详情

数据结构面试题及答案讲解:二叉树专题(上)(代码片段)

...)2、判断一个二叉树是否是高度平衡的二叉树。(2020年字节跳动面试真题)3、根据一棵树的前序遍历与中序遍历构造二叉树(Leetcode105题)1、求二叉树的最大深度。OJ链接:https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/su 查看详情

字节跳动高频算法题top100

题目出现次数3.无重复字符的最长子串10625.K个一组翻转链表84206.反转链表83215.数组中的第K个最大元素81146.LRU缓存机制68103.二叉树的锯齿形层次遍历6415.三数之和62121.买卖股票的最佳时机61160.相交链表581.两数之和48236.二叉树的最... 查看详情

字节跳动高频算法题top100

题目出现次数3.无重复字符的最长子串10625.K个一组翻转链表84206.反转链表83215.数组中的第K个最大元素81146.LRU缓存机制68103.二叉树的锯齿形层次遍历6415.三数之和62121.买卖股票的最佳时机61160.相交链表581.两数之和48236.二叉树的最... 查看详情

字节跳动大数据研发岗位面试题目

java题求平方根,返回类型是整数,结果只保留整数的部分,小数部分将被舍去sql题目基础的编程语言数据结构和算法MySql和Hive的区别除了同样是存储数据的工具,再无其他的相同之处,1.存储位置不同RDBMSHDFS2.... 查看详情

字节跳动大数据研发岗位面试题目

java题求平方根,返回类型是整数,结果只保留整数的部分,小数部分将被舍去sql题目基础的编程语言数据结构和算法MySql和Hive的区别除了同样是存储数据的工具,再无其他的相同之处,1.存储位置不同RDBMSHDFS2.... 查看详情

字节跳动大数据开发面试题-附答案(代码片段)

此面试题来自牛客网友分享的字节跳动应届一面,面试时长一小时。网友情况:985本硕。参考答案由本公众号提供。如有错误,欢迎指正!以下为面试过程中提问,岗位为大数据开发:自我介绍+项目介... 查看详情

字节跳动大数据研发面试——自我反省

一、面试问题自我介绍balabala…1.1提问线程与进程的理解。具体比如…系统总线怎么理解网络爬虫的通信过程,需要经历哪些过程怎么通过链接找到服务器IP的域名解析怎么理解。TCP/UDP怎么区别。TCP三次握手GET/PUT区别系统负... 查看详情

数据结构二叉树相关面试题java版leetcode题-------二叉树(代码片段)

文章目录基础面试题第一题:二叉树的前序遍历。(递归解法)(迭代解法)第二题:二叉树的中序遍历。(递归解法)(迭代解法)第三题:二叉树的后序遍历。(递归解法)(迭代解法)第四题:相同的树解题思路:代码实现:第五题:另一棵树的子... 查看详情

二叉树相关面试题数据结构(代码片段)

题目目录基础面试题二叉树的前序遍历二叉树的中序遍历二叉树的后续遍历结果相同的树另一棵树的子树二叉树的最大深度平衡二叉树判断对称二叉树进阶面试题二叉树的遍历及构建二叉树的分层遍历二叉树的最近公共祖先二叉... 查看详情

124.二叉树中的最大路径和-字节跳动高频题(代码片段)

一、题目描述路径被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点,且不一定经过根节点。路径和是路径中各... 查看详情

一次字节面试,被二叉树的层序遍历捏爆了(代码片段)

前言大家好,我是bigsai,在数据结构与算法中,二叉树无论是考研、笔试都是非常高频的考点内容,在二叉树中,二叉树的遍历又是非常重要的知识点,今天给大家讲讲二叉树的层序遍历。这部分很多人可... 查看详情

一次字节面试,被二叉树的层序遍历捏爆了(代码片段)

前言大家好,我是bigsai,在数据结构与算法中,二叉树无论是考研、笔试都是非常高频的考点内容,在二叉树中,二叉树的遍历又是非常重要的知识点,今天给大家讲讲二叉树的层序遍历。这部分很多人可... 查看详情

199.二叉树的右视图-字节跳动高频题(代码片段)

一、题目描述给定一个二叉树的根节点root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。示例1:输入:[1,2,3,null,5,null,4]输出:[1,3,4]示例2:输入:[1,null,3]输出:[1,3]示例3:... 查看详情

2022暑期实习字节跳动数据研发面试经历

🌟今天下午面试两家,字节跳动数据研发一面和百度三面,百度那边突然不面了,hr说下个星期再看看,是直接过了还是再来一面,需要和部门商量一下,先来总结一下字节跳动的面试,对百度面... 查看详情

java集合与数据结构——二叉树02

文章目录Java集合与数据结构——二叉树(二)初阶面试题二叉树的前中后遍历前序遍历中序遍历后序遍历获取二叉树的高度获取二叉树的最大深度求整颗二叉树的叶子节点数量遍历思路:子问题思路:查找二叉树中对应val... 查看详情

java实习生每日10道面试题打卡!(代码片段)

打卡Day28,贵在坚持,要学的还有很多,有限的时间,尽可能多学一些总没坏处!1、满二叉树、完全二叉树、平衡二叉树、红黑树、二叉搜索树的区别?参考文章:树、二叉树(完全二叉树、满二叉树)... 查看详情