如何在O（n）时间内遍历二进制树，而不需要额外的内存 [英] How to traverse a binary tree in O(n) time without extra memory

问题描述

给定一个具有整数的二叉树，Left&右指针，如何在O（n）时间和O（1）额外的内存（没有堆栈/队列/递归）中遍历树？

这个人给出了一个解决方案，它不是O（n）编码当前路径的总时间作为一个整数（因此适用于有限深度的树木）。

我正在寻找经典的解决方案

（SPOILER）

编码孩子中每个节点的父节点。

解决方案

任何好的算法书都会有这个算法，看看例如在Knuth（TAOCP I.2.3.1遍历二叉树，练习21）。但是，因为这个算法修改树，所以必须在多线程环境中使用极端注意。

你也可以使用线程树（见Knuth）。

Given a binary tree with an integer, Left & Right pointers, how can one traverse the tree in O(n) time and O(1) extra memory (no stack/queue/recursion)?

This guy gave a solution which is not O(n) total time that encoded the current path as an integer (and thus works on for trees of limited depth).

I am looking for the classical solution

(SPOILER)

that encoded the parent of each node in the children.

解决方案

Any good algorithm book will have this algorithm, look e.g. in Knuth (TAOCP I.2.3.1 Traversing binary trees, excercise 21). However, because this algorithm modifies the tree in place, you must use extreme caution in a multi-threaded environment.

You might also use threaded trees (see in Knuth).

这篇关于如何在O（n）时间内遍历二进制树，而不需要额外的内存的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！