那些年我们一起遍历过的树

这篇博文想和大家讨论一下tree的traversal有哪些方法。当然我们都很熟悉DFS(InOrder, PreOrder, PostOrder)和BFS,这篇我们想谈一下一些其他方法以及DFS BFS的变种

[可以识辨每层的BFS]

[细节]

在题目中,我们时常需要做BFS并且要区分树的层与层,然后利用这个信息完成任务

[做法]

使用一个queue

初始化queue里插入root和一个分割符(普通node是pointer,因此分割符可选用特殊数字)

pop出root, 像通常BFS一样遍历root的child node,当dequeue分隔符时,在queue里后面插入分隔符

这样遍历完整棵树

[例题]

Populating Next Right Pointers in Each Node --[From Leetcode]

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

  • You may only use constant extra space.

For example,

Given the following binary tree,

1 / \ 2 3 / \ \ 4 5 7

After calling your function, the tree should look like:

1 -> NULL / \ 2 -> 3 -> NULL / \ \ 4-> 5 -> 7 -> NULL

......

原文发布于微信公众号 - 包子铺里聊IT(baozitraining)

原文发表时间:2014-07-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mathor

二分查找与二分答案(3)

1604
来自专栏Golang语言社区

golang使用sort接口实现排序示例

今天看见群里再讨论排序的sort.Interface的实现,有童鞋一直搞不定,我就上手了一下,哦耶搞定了,代码放在这里. 其实很简单sort.Interface...

3737
来自专栏Script Boy (CN-SIMO)

软件工程个人作业01

题目:      像二柱子那样,花二十分钟写一个能自动生成三十道小学四则运算题目的 “软件”,要求:除了整数以外,还要支持真分数的四则运算(需要验证结果的正确...

2170
来自专栏海天一树

程序员必须掌握的8大排序算法

分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基数排序)...

3188
来自专栏机器学习与自然语言处理

用只含一个链域的节点实现循环链表的双向遍历

通常来说,要实现循环双向链表,每个节点需要有两个链域:前驱和后继。现在的问题是:如何设计一种环形表,使表的每个结点只包含一个链域而又能够有效地对其进行两个方向的...

2115
来自专栏有趣的Python

8-玩转数据结构-堆

前面我们介绍了二分搜索树,以及通过二分搜索树实现的集合和映射这两个更加高层次的数据结构。

3111
来自专栏友弟技术工作室

golang之Struct什么是结构体struct?

最近在复习golang,学习的东西,如果不使用,很快就会忘记。所以,准备复习完golang,做一个练手的小项目,加深对golang的学习。今天开始公司,进入封闭...

5626
来自专栏jeremy的技术点滴

py3_cookbook_notes_01

3198
来自专栏Golang语言社区

实效go编程--2

Go函数的返回值或结果“形参”可被命名,并作为常规变量使用,就像传入的形参一样。 命名后,一旦该函数开始执行,它们就会被初始化为与其类型相应的零值; 若该函数执...

3377
来自专栏PPV课数据科学社区

【工具】SAS数据整理的16个技巧

1、修改属性   attrib 2、根据条件删除记录   if条件 then delete; 3、分拆数据集 data mastermissing; me...

3415

扫码关注云+社区