文档章节

IT公司100题-tencent-打印所有高度为2的路径

关西大汉弹琵琶
 关西大汉弹琵琶
发布于 2016/01/06 15:40
字数 231
阅读 49
收藏 3

问题描述:

打印所有到叶子节点长度为2的路径

    10

   /  \

  6   16

  / \   / \

 4 8  14 18

  / \    / \    \

2  5  12 15 20

   /

  11

 

打印:

[10 6 8]

[6 4 2]

[6 4 5]

[16 14 15]

[16 18 20]

[14 12 11]

问题分析:

中序遍历树,每一个节点检查有无高度为2的路径

代码实现:

//IT27 start
private LinkedList<BSTreeNode> lst = new LinkedList<BSTreeNode>();
public void findDepthPath(int depth){
   findDepthPath(root, depth);
}
private void findDepthPath(BSTreeNode bsTreeNode, int expected){
   //inorder traversal tree
   //checkNode for each node
   checkNode(bsTreeNode, expected);
   if(bsTreeNode.left != null)
      findDepthPath(bsTreeNode.left, expected);
   if(bsTreeNode.right != null)
      findDepthPath(bsTreeNode.right, expected);
}
//Find all the expected depth leaf and print path
private void checkNode(BSTreeNode bsTreeNode, int expected){
   lst.addLast(bsTreeNode);
   if(isLeaf(bsTreeNode) && expected == 0) {
      System.out.println("Get: ");
      for (int i = 0; i < lst.size(); i++) {
         System.out.print(lst.get(i).value + " ");
      }
      System.out.println();
   }
   if(bsTreeNode.left != null && expected > 0) {
      checkNode(bsTreeNode.left, --expected);
      ++expected;
   }
   if(bsTreeNode.right != null && expected > 0) {
      checkNode(bsTreeNode.right, --expected);
      ++expected;
   }
   lst.removeLast();
}
//IT27 end


代码输出:

Get: 
10 6 8 
Get: 
6 4 2 
Get: 
6 4 5 
Get: 
16 14 15 
Get: 
16 18 20 
Get: 
14 12 11


© 著作权归作者所有

关西大汉弹琵琶
粉丝 8
博文 41
码字总数 14221
作品 0
浦东
程序员
私信 提问
分享一个面试经历(Delphi)

首先是对方公司的人事打电话来咨询情况,声音甜甜的,感觉是一个二十多点儿的妹子,声音真甜!!! 因我本人目前在北京工作,对方是成都公司,所以对方问了一些基本情况以及是否准备去成都发...

张乐1024
2015/10/15
643
0
程序员面试题100题(一)

题目选自以下博客网址: http://zhedahht.blog.163.com/#。 第26题: 题目:输入一个正数n,输出所有和为n连续正数序列。 例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以输出3个连续序列1-5...

hoodlum1980
2007/07/13
0
0
[算法总结] 20 道题搞定 BAT 面试——二叉树

本文首发于我的个人博客:尾尾部落 0. 几个概念 完全二叉树:若二叉树的高度是h,除第h层之外,其他(1h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没...

繁著
2018/09/04
0
0
科技公司9大古怪面试题:如何解决世界饥饿问题

科技公司在面试求职人员时通常会问到一些奇怪的问题,希望以此挑战求职者的思维。这些问题会迫使求职者抛开事先准备好的一些说法,即兴想出问题的解决方案。不过,这些奇怪的问题在一定程度上...

虫虫
2011/12/28
4.7K
52
十小时搞定二叉树面试之DFS方法(Python)

数据工程师惯用python,然而数据结构还是c++或者java比较经典。这就造成很多朋友并不太习惯。本文就从《剑指offer》这本书中的经典题型出发,来研究探讨一下python 刷数据结构题型的一些惯用...

香橙云子
09/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Podman 使用指南

> 原文链接:Podman 使用指南 Podman 原来是 CRI-O 项目的一部分,后来被分离成一个单独的项目叫 libpod。Podman 的使用体验和 Docker 类似,不同的是 Podman 没有 daemon。以前使用 Docker...

米开朗基杨
44分钟前
5
0
拯救 项目经理个人时间的5个技巧

优秀的项目经理都有一个共同点,那就是良好的时间管理能力。专业的项目经理会确保他们的时间投入富有成效,尽可能避免时间浪费。 时间管理叫做GTD,即Getting Things Done——“把事情做完”...

Airship
今天
6
0
LNMP环境介绍,Mariadb安装,服务管理,mariadb安装3

LNMP环境介绍 Nginx 处理的请求有两种,分为 静态与动态 图片,js,css,视频,音频,flash 等都是静态请求,这些数据都不是保存在数据库里面的 动态请求一般来说,需要的数据是在数据库里面...

doomcat
今天
1
0
前端技术之:Prisma Demo服务部署过程记录

安装前提条件: 1、已经安装了docker运行环境 2、以下命令执行记录发生在MackBook环境 3、已经安装了PostgreSQL(我使用的是11版本) 4、Node开发运行环境可以正常工作 首先需要通过Node包管...

popgis
今天
7
0
数组和链表

数组 链表 技巧一:掌握链表,想轻松写出正确的链表代码,需要理解指针获引用的含义: 对指针的理解,记住下面的这句话就可以了: 将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指...

code-ortaerc
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部