无需额外的内存如何遍历一个二叉树O（n）时间 [英] How to traverse a binary tree in O(n) time without extra memory

问题描述

考虑到与一个整数二叉树，左，放大器;右指针，一个人如何可以遍历O（n）时间及O（1）额外的内存（没有堆栈/队列/递归）？

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)?

这家伙给了一个解决方案，这是不是O（n）的总时间是连接codeD当前路径作为一个整数（因此适用于有限深度的树）。

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).

我要寻找的经典解

（剧透）

这EN codeD在孩子的每个节点的父节点。

that encoded the parent of each node in the children.

推荐答案

任何优秀算法的书都会有这个算法，看看如在高德纳（TAOCP I.2.3.1遍历二叉树，锻炼; Tibial 21）。但是，由于该算法修改了树的地方，你必须在多线程环境中使用的极端的注意事项。

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屋！