文档章节

IT公司100题-1-二叉树转换为双链表

关西大汉弹琵琶
 关西大汉弹琵琶
发布于 2015/10/19 18:29
字数 357
阅读 94
收藏 8
点赞 0
评论 0

问题描述:

输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点,只调整指针的指向。

    10
   /   \
  6      14
/  \    /   \
4   8 12    16

转换成双向链表
4=6=8=10=12=14=16。

分析:

首先我们定义的二元查找树 节点的数据结构如下:

private static class BSTreeNode{
   BSTreeNode(int x, BSTreeNode lt, BSTreeNode rt)
   {value = x; left = lt; right = rt;}

   int value;
   BSTreeNode left;
   BSTreeNode right;
}

代码实现:

package oschina.IT100;

/**
 * @project: oschina
 * @filename: IT1.java
 * @version: 0.10
 * @author: JM Han
 * @date: 14:55 2015/10/19
 * @comment: 将该二元查找树转换成一个排序的双向链表
 * @result:
 */
class BSTree1 {
   private static class BSTreeNode{
      BSTreeNode(int x, BSTreeNode lt, BSTreeNode rt)
      {value = x; left = lt; right = rt;}

      int value;
      BSTreeNode left;
      BSTreeNode right;
   }

   private BSTreeNode root;
   private BSTreeNode head;
   private BSTreeNode last;

   public BSTree1(){root = null; head = null; last = null;}

   public void insert(int value){
      root = insert(root, value);
   }

   private BSTreeNode insert(BSTreeNode t, int value) {
      if (null == t)
         return new BSTreeNode(value, null, null);

      if (t.value > value)
         t.left = insert(t.left, value);
      else if (t.value < value)
         t.right = insert(t.right, value);
      else
         System.out.println("already exist");
      return t;
   }

   public void treeToList(){
      treeToList(root);
   }

   private void treeToList(BSTreeNode root){
      if(null == root)
         return;
      treeToList(root.left);
      //previous pointer
      root.left = last;
      if(null == last)
         head = root;
      else
         //next pointer
         last.right = root;
      //last is the current root node
      last = root;
      treeToList(root.right);
   }

   public void printList(){
      if(null == head)
         return;
      while(head != null) {
         System.out.println(head.value);
         head = head.right;
      }
   }
}

public class IT1 {
   public static void main(String[] args) {
      BSTree1 bsTree = new BSTree1();
      bsTree.insert(10);
      bsTree.insert(6);
      bsTree.insert(14);
      bsTree.insert(4);
      bsTree.insert(8);
      bsTree.insert(12);
      bsTree.insert(16);
      bsTree.treeToList();
      bsTree.printList();
   }
}

输出:

4
6
8
10
12
14
16


© 著作权归作者所有

共有 人打赏支持
关西大汉弹琵琶
粉丝 7
博文 41
码字总数 14221
作品 0
浦东
程序员
2015年1月9日XX大学XX学院考试题

复习 一、选择题 1.计算机算法指的是 。 A.计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 2. 下面关于算法说法正确的是( ) A.算法最终必须由计算机程序实现 B. 为解决某问题的...

请叫我赵小宝
2015/01/09
0
0
二叉树常见面试题

树是一种比较重要的数据结构,尤其是二叉树。二叉树是一种特殊的树,在二叉树中每个节点最多有两个子节点,一般称为左子节点和右子节点(或左孩子和右孩子),并且二叉树的子树有左右之分,其...

笨拙的小Q
2016/09/22
34
0
微软等公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / / 6 14 / / / / 4 ...

chambai
2012/08/05
0
0
Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛
2017/11/10
0
0
python剑指offer66题

二维数组的查找 替换空格 从头到尾打印链表 重建二叉树 用两个栈实现队列 选择数组中的最小数字 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 二进制中1的个数 数值的整数次方 调整数组顺序使奇...

lyy0905
06/03
0
0
各大公司(Google,Microsoft,Baidu, Microsoft Research Asia etc.)实习生面试题总汇

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / 6 14 / / 4 8 12 1...

云栖希望。
2017/12/04
0
0
算法之路

最近在GitHub上看到的某位学友的算法学习规划,贴过来与各位共勉。有新的内容可以文末留言补充。 学习方法 把所有经典算法写一遍 看算法有关源码 加入算法学习社区,相互鼓励学习 看经典书籍...

李序锴
2017/11/08
0
0
二叉树链接右指针II

原题   Follow up for problem “Populating Next Right Pointers in Each Node”.   What if the given tree could be any binary tree? Would your previous solution still work?   ......

一贱书生
2016/12/22
1
0
排序链表转换成二叉排序树

原题   Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. 题目大意   给定一个升序的单链表,将它转换成一颗高度平衡的...

一贱书生
2016/12/21
0
0
C++学习笔记(三)

面试题:替换空格 题目:实现一个函数,把字符串中的每个空格替换成“%20”,例如输入“We are happy.”,则输出“Wr%20are%20happy.”。典型应用:网络编程中,若URL参数含有特殊字符(空格...

初雪之音
2016/01/10
51
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Confluence 6 配置 HTTP 超时设置

当宏,例如 RSS Macro 进行 HTTP 请求的时候,有可能因为请求的时间比较长,而导致超时。你可以通过设置系统参数来避免这个问题。 配置 HTTP 超时设置: 在屏幕的右上角单击 控制台按钮 ,然...

honeymose
9分钟前
0
0
我的第一篇博文

网络界的前辈们好。本人从接触网络到你现在也有4、5年的时间了,期间不断的通过网络学习,当然也没少看大牛们给的建议。 2011年的9月份,如愿以偿的上了“大学”,刚上大学就接触到了一门叫做...

yeahlife
23分钟前
0
0
第十四章NFS服务搭建与配置

14.1 NFS介绍 NFS介绍 NFS是Network File System的缩写;这个文件系统是基于网路层面,通过网络层面实现数据同步 NFS最早由Sun公司开发,分2,3,4三个版本,2和3由Sun起草开发,4.0开始Netap...

Linux学习笔记
28分钟前
0
0
双向认证-nginx

1、设置容器 docker run -it --name nginx-test2 -v /home/nginx:/apps -v /home/nginx/conf/nginx.conf:/etc/nginx/nginx.conf:ro -p 8183:80 -p 7443:443 -d nginx:stable 2、修改nginx配......

hotsmile
29分钟前
0
0
深入了解 Java 自动内存管理机制及性能优化

一图带你看完本文 一、运行时数据区域 首先来看看Java虚拟机所管理的内存包括哪些区域,就像我们要了解一个房子,我们得先知道这个房子大体构造。根据《Java虚拟机规范(Java SE 7 版)》的规...

Java大蜗牛
31分钟前
4
0
SpringBoot | 第六章:常用注解介绍及简单使用

前言 之前几个章节,大部分都是算介绍springboot的一些外围配置,比如日志 配置等。这章节开始,开始总结一些关于springboot的综合开发的知识点。由于SpringBoot本身是基于Spring和SpringMvc...

oKong
32分钟前
7
0
云数据库架构演进与实践

如今,大型企业如金融企业和银行等,在下一代的微服务架构转型要求下,需要基础软件和数据平台能够实现原生的云化,以满足微服务架构的需求。 微服务,也就是一种面向服务的,有特定边界的松...

巨杉数据库
33分钟前
0
0
Linux系统梳理---系统搭建(一):jdk卸载与安装

1.去官网下载符合Linux版本的jdk,暂用jdk-8u171-linux-x64.rpm 2.登陆Linux,进入usr目录,创建java目录(方便管理,可以其他位置):mkdir java 3.上传下载的jdk包至Linux服务器,使用rz指令(sz f...

勤奋的蚂蚁
43分钟前
0
0
Linux Kernel 4.16 系列停止维护,用户应升级至 4.17

知名 Linux 内核维护人员兼开发人员 Greg Kroah-Hartman 近日在发布 4.16.18 版本的同时,宣布这是 4.16 系列的最后一个维护版本,强烈建议用户立即升级至 4.17 系列。 Linux 4.16 于 2018 年...

六库科技
45分钟前
0
0
JVM 堆内存设置 -Xmx -Xms

在Tomcat的启动参数里可以设置,如下 参数说明: -Xmx Java Heap最大值,默认值为物理内存的1/4,最佳设值应该视物理内存大小及计算机内其他内存开销而定; -Xmx 此设置控制 Java 堆的最大大...

不开心的时候不要学习
48分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部