向内螺旋树遍历
Inward spiral tree traversal
我遇到了一个有趣的问题：
Given a binary tree print it in inward spiral order i.e first print level 1, then level n, then level 2, then n-1 and so on.
For Ex:
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
Should Output:
1 15 14 13 12 11 10 9 8 2 3 7 6 5 4
我想到了解决办法：
将每个级别的元素存储在一个列表中
列表[0] = [1]
列表[1] = [2, 3]
列表[2] = [4, 5, 6, 7]
列表[3] = [8, 9, 10, 11, 12, 13, 14, 15]
按要求的顺序循环遍历列表列表（0、n-1、1、n-2、...）并打印。这里 n 是级别数，在上述情况下为 4。
它的 space 复杂度为 O(n)。我确信可能有更好的解决方案，具有更好的 space 复杂性，但我无法想象它是否存在。有人有任何指示吗？
你不需要逐级存储节点，你可以通过将所有节点存储在一个deque structure中来解决任务，并在数组中维护节点的级别。
Deque <Integer> deque = new LinkedList();
Queue <Integer> q = new LinkedList();
int[]level = new int[n];//we need to store the level of each node, n is number of node
q.add(0);//Adding the root node
while(!q.isEmpty()){
int node = q.deque();
for(int child : getNodeChildren(node)){
level[child] = level[node] + 1;//Keep track the level of child node
q.add(child);
deque.add(child);//Store the child node into the queue.
}
}
// Print output
boolean printHead = true;
while(!deque.isEmpty()){
if(printHead){
int node = deque.pollFirst();
print node;
//Check if we already printed every node in this current level,
//if yes, we need to switch to print from the end of the queue
if(!deque.isEmpty() && level[deque.getFirst()] != level[node]){
printHead = false;
}
}else{
int node = deque.pollLast();
print node;
if(!deque.isEmpty() && level[deque.getLast()] != level[node]){
printHead = true;
}
}
}
代码逻辑为：
我们从deque开始一直打印，如果下一个节点和上一个打印的节点不在同一层级，这也意味着我们刚刚打印了当前层级的所有元素，我们需要切换到从deque结尾开始打印，反之亦然。我们继续这个过程，直到所有节点都被打印出来。
Space复杂度为O(n)，时间复杂度为O(n)。
首先我要感谢发帖人提出的问题，并提供一个时间复杂度和 space 复杂度如何相互对立的实际例子。给定大量 space，您的算法可以非常快（因为您可以创建 'state'）。相反，如果你在 space 中非常受限，你会发现有必要执行额外的迭代来弥补状态的不足。
事实证明，这个问题在space复杂度O(n)下很容易解决。如果您被允许为结果 (O(n)) 创建 space，则有几种算法可以创建时间复杂度 O(n) 的解决方案。发布了一个解决方案（我喜欢），我还提供了一种不同的、也许是优雅的方法来解决 O(n) 和时间复杂度 O(n)；参考方法solveOrderN().
挑战在于如何在小于 O(n) 的 space 复杂度中找到解决方案。为此，不得允许您创建结果 space，因此您被迫在问题中给出的树 space 内操作。你被迫交换元素。
我提供的解决方案——solveSubOrderN()——没有产生任何结果space；答案在与问题相同的内存 space 中返回。
我非常乐观地认为我可以在 O(log base 2(n)) 甚至接近 O(n) 的时间复杂度内解决这个问题。但是经过多方分析，我不能这么激进。
当你开始交换元素时，当你绕回 non-processable 元素时，你最终会碰到一个 'halting condition'。如果这个暂停不存在，你可以达到 O(log base 2 n)。但是你无法避免它。因此，为了弥补这一点，我不得不创建一些 space（布尔数组）来表示正在处理的元素的状态。
我想讨论这个布尔状态与为 result/solution 创建 space 有何不同。当您创建解决方案（n 个元素，大小为 s）时，您正在创建 space=n*s。在这个问题中，s 是一个整数。通常 s 可能非常大，这使它成为一个 'expensive'' 过程（也是发帖人造成此问题的原因）。布尔数组的 space 相当少，随着 s 大小的增长甚至可以忽略不计（即 n/s 随着 s 的增长接近 0）。
事实证明，当 space 复杂度小于 O(n) 时，您无法实现时间复杂度 O(n)。当您遇到停止条件时，您将被迫再次迭代。但事实证明，对于一棵二叉树来说，额外的迭代次数很少（而且每次迭代都是为了简单地找到下一个起点）。
所以综上所述，请找到以下两个解决方案；一个具有 space 复杂度 O(n) 和时间复杂度 O(n)，但更重要的是一个 space 复杂度低于 O(n)，时间复杂度非常接近 O(n ).
public class BinaryTree {
public static void main(String[] args) {
int treeN2[] = {1, 2, 3};
int treeN3[] = {1, 2, 3, 4, 5, 6, 7};
int treeN4[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
int treeN5[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31};
int answer[] = solveOrderN(treeN5);
System.out.println(Arrays.toString(answer));
solveSubOrderN(treeN5);
System.out.println(Arrays.toString(treeN5));
}
/**
* Given a binary tree, Perform inward spiral tree traversal.<br>
* With this approach, there is no space created for the result.
* All manipulation is done within the original tree<br>
* Some space is created (boolean[n]) to add necessary state of processing.
* Space Complexity: Less than O(n), greater than log(base2)(n)
* Time Complexity: Slightly greater than O(n)
* @param tree Input tree
*/
public static void solveSubOrderN(int tree[]) {
boolean complete[] = new boolean[tree.length];
Arrays.fill(complete, false);
System.out.println("Solving Sub O(n); tree size="+tree.length);
int n = log2Round(tree.length+1);
if (n == 1)
return;
int o[] = getLevelOffsets(n);
System.out.println("Number of levels="+n);
int pos = 0;
complete[0] = true;
int currentValue = 0;
int moves=1;
while (moves < tree.length) {
pos = getStartingPos(complete);
currentValue = tree[pos];
tree[pos] = 0;
while (true) {
int nextPos = getTargetPosition(pos, o, n);
int nextValue = tree[nextPos];
tree[nextPos] = currentValue;
complete[nextPos] = true;
currentValue = nextValue;
pos = nextPos;
moves++;
if (currentValue == 0)
break;
}
}
}
/**
* Given a binary tree, Perform inward spiral tree traversal.
* Space Complexity: O(n)
* Time Complexity: O(n)
* @param tree Input tree
* @return The solution
*/
public static int[] solveOrderN(int tree[]) {
int answer[] = new int[tree.length];
int n = log2Round(tree.length+1);
int o[] = getLevelOffsets(n);
System.out.println("Solving O(n); tree size="+tree.length);
System.out.println("Number of levels="+n);
for (int i = 0; i < tree.length; i++) {
answer[getTargetPosition(i, o, n)] = tree[i];
}
return answer;
}
/**
* Search for the first unprocessed element
* @param complete An array of boolean (true = processed)
* @return
*/
public static int getStartingPos(boolean[] complete) {
for (int i=0; i<complete.length; i++) {
if (!complete[i])
return i;
}
return 1;
}
public static int getTargetPosition(int pos, int o[], int n) {
int row = getRow(pos);
int rowOrder = getRowOrder(row, n);
boolean isReversed = isBottom(row, n);
int posInRow = getPosInRow(pos, n);
int rowOffset = getRowOffset(rowSize(row), posInRow, isReversed);
return o[rowOrder]+rowOffset;
}
public static int getRowOffset(int rowSize, int posInRow, boolean isReversed) {
if (!isReversed)
return posInRow;
else
return rowSize-posInRow-1;
}
public static int rowSize(int row) {
return exp(row, 2);
}
public static int getPosInRow(int pos, int n) {
int row = getRow(pos);
return pos-(exp(row,2)-1);
}
/**
* The top n/2 rows print forward, the bottom n/2 rows print reversed
* @param row Zero based row [0 to n-1]
* @param n Number of levels to the tree
* @return true if line should be printed forward, false if reversed
*/
public static boolean isBottom(int row, int n) {
int halfRounded = n/2;
return (row <= n-halfRounded-1) ? false : true;
}
public static int exp(int n, int pow) {
return (int)Math.pow(pow, n);
}
public static double log2(int n) {
return (Math.log(n) / Math.log(2));
}
public static int log2Round(int n) {
return (int)log2(n);
}
/**
* For a given position [0 to N-1], find the level on the binary tree [0 to n-1]
* @param pos Zero based position in the tree (0 to N-1)
* @return Zero based level (0 to n-1)
*/
public static int getRow(int pos) {
return log2Round(pos+1);
}
/**
* For a given row [0 to n-1], find the order in which that line would be processed [1 to log base 2 n]
* @param row The row in the tree [0 to n-1]
* @return The order that row would be processed [0 to n-1]
*/
public static int getRowOrder(int row, int n) {
return isBottom(row, n) ? (n-row-1)*2+1 : row*2;
}
public static int getRowForOffset(int row, int n) {
boolean isOdd = row%2 == 1;
return isOdd ? n-(row-1)/2 - 1 : row/2;
}
/**
* Compute the offset for a given ordered row
* @param n The number of levels in the tree
* @return Generated offsets for each row (to keep time complexity at O(n))
*/
public static int[] getLevelOffsets(int n) {
int o[] = new int[n];
Arrays.fill(o, 0);
o[0] = 0;
int offset = 0;
for (int i=0; i<n; i++) {
int nextRow = getRowForOffset(i, n);
o[i] = offset;
offset += exp(nextRow, 2);
}
return o;
}
}
这是一个用O(1)space和O(n * h)时间的简单解决方案，其中n是节点数，h是树高。保留两个指向当前层次的变量进行打印，然后根据长度对应合适的树深度的二进制字符串遍历树后打印每个节点；向左走“0”，向右走“1”（例如，示例中的 left-most 节点由“000”到达，其邻居位于“001”）。由于要打印一个节点，我们最多需要进行 h 次迭代，时间复杂度为 O(n * h).
下面是稍微详细一点的算法：
down = 0
up = tree height
while:
if down > up:
break
else:
set exp to down then up (or only one if up == down):
for i = 0 to 2^exp - 1:
s = binary string i, padded to exp digits
traverse tree according to s
if a node exists by the end of s:
print node
down = down + 1
up = up - 1
我不确定它是否会快一个数量级，但您可以使用相同的原则在树中行走，而不是从每个节点的根开始：返回直到“0”遇到，将其翻转为“1”，然后一直向左保持下降到目标层级，递归重复，直到字符串全为“1”。例如，目标级别 4：
0000 => (000)1 => (00)10 => (001)1 => (0)100...etc.
你可以在没有明显额外的情况下解决它 space，但它需要 O(n)。时间复杂度取决于二叉树的表示。
如果你有一个数组，时间复杂度将是 O(n)，例如：
public static void main(String[] args) {
int[] binaryTree = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
int nodes = binaryTree.length;
int levels = (int) Math.ceil(Math.log(nodes) / Math.log(2));
int[] increment = {1, -1};
int index = 0;
for (int i = 0; i < levels; i++) {
int level = (index) * levels + increment[index] * (i / 2) - index;
int begin = (int) Math.round(Math.pow(2, level));
int[] range = {begin, 2 * begin - 1};
for (int j = range[index]; j != range[1 - index]; j += increment[index]) {
System.out.print(" " + binaryTree[j-1]);
}
System.out.print(" " + binaryTree[range[1 - index]-1]);
index = 1 - index;
}
System.out.println();
}
如果您有一个二叉树，其节点定义为：
publi class Node {
Node[] children;
int value;
}
时间复杂度（没有额外的 space）将为 O(n*log(n))。
示例：
public class BinaryNode {
BinaryNode[] children = {null, null};
int value;
public BinaryNode(int value) {
this.value = value;
}
private int getRecursive(int reference) {
int result = value;
if (reference > 1) {
result = children[reference%2].getRecursive(reference/2);
}
return result;
}
public int get(int p) {
int reference = 1;
int p2 = p;
while (p2 > 1){
reference = (reference << 1) + (p2 & 1);
p2 >>= 1;
}
return getRecursive(reference);
}
private void generateLevels(int levels){
if (levels > 0){
children[0] = new BinaryNode(value*2);
children[0].generateLevel(levels -1);
children[1] = new BinaryNode(value*2+1);
children[1].generateLevel(levels -1);
}
}
public static BinaryNode generate(int levels){
BinaryNode result = null;
if (levels > 0){
result = new BinaryNode(1);
result.generateLevels(levels - 1);
}
return result;
}
public static void main(String[] args) {
int levels = 5;
BinaryNode btreeRoot = BinaryNode.generate(levels);
int[] increment = {1, -1};
int index = 0;
for (int i = 0; i < levels; i++) {
int level = (index) * levels + increment[index] * (i / 2) - index;
int begin = (int) Math.round(Math.pow(2, level));
int[] range = {begin, 2 * begin - 1};
for (int j = range[index]; j != range[1 - index]; j += increment[index]) {
System.out.print(" " + btreeRoot.get(j));
}
System.out.print(" " + btreeRoot.get(range[1 - index]));
index = 1 - index;
}
System.out.println();
}
}
编辑
如何用 n 计算 h？
简单：
h = log2(n)
因此，时间复杂度：O(n * log n) == O(n * h)。
算法在O(log(n))中获取一个元素，需要获取所有(n个元素)所以，结果时间复杂度为O(n * log(n))。
该算法无需额外 space.
BtreeRoot为原始二叉树，算法按正确顺序获取所有节点，计算level中的下一层。 level 在 O(1)（log2(n) 次）中转到值 (1, levels -1, 2, levels - 2)
在每一层中，算法获得其m个节点：从2^level到2^(level +1) - 1。所有级别的总和为n（节点数），
根据级别（奇数或对数），从头到尾或反向计算当前节点位置。那么就知道当前节点要打印的位置，需要取值，在完美二叉树中，需要Log(n)。
通过说您的 space 复杂度 < O(n)，您似乎在假设树的表示方式，然后您无法使用任何其他数据来扩充该表示and/or 解决方案中的结构（即 O(n)）。
对于我的回答，我将假设树是完整的（或至少是平衡的），其中平衡意味着树的高度是 O(logN)。
在此假设下，我们可以将树存储在堆数据结构中。在这个结构中，节点数据存储在一个数组中，其中，层级排列：
[0][1][1][2][2][2][2][3][3][3][3][3][3][3][3]...
如果树中不存在该节点，则数组中的给定位置将具有指向节点数据的指针或指向 NULL 的指针。
本例中 space 的数量是 O(2^L)，其中 L 是树中的层数。在平衡树中，L = O(log(N))，所以这个表示的大小是O(N).
同样假设我们知道这个数组的大小，那么树的层数是ceiling(log_2(size)).
假设 Levels 从 0...K-1 开始，数组中任何级别的起始位置为：2^L - 1.
这是算法的伪代码。
PrintLevel( Array<Node> heap, level) {
int levelStart = power( 2, level ) - 1;
int nextLevelStart = (levelStart + 1) * 2 - 1; // same as power( 2, level+1 ) - 1
for( int i = levelStart; i < nextLevelStart; i++ ) {
if( heap[i] != NULL ) {
print( heap[i] );
}
}
}
SpiralPrint( Array<Node> heap ) {
int lowLevel = Ceil(Log(heap.size())) - 1
int highLevel = 0
while( lowLevel >= highLevel ){
PrintLevel( heap, highLevel );
if (lowLevel > highLevel)
PrintLevel( heap, lowLevel );
highLevel += 1;
lowLevel -= 1;
}
}
我遇到了一个有趣的问题：
Given a binary tree print it in inward spiral order i.e first print level 1, then level n, then level 2, then n-1 and so on.
For Ex:
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
Should Output:
1 15 14 13 12 11 10 9 8 2 3 7 6 5 4
我想到了解决办法：
将每个级别的元素存储在一个列表中
列表[0] = [1]
列表[1] = [2, 3]
列表[2] = [4, 5, 6, 7]
列表[3] = [8, 9, 10, 11, 12, 13, 14, 15]按要求的顺序循环遍历列表列表（0、n-1、1、n-2、...）并打印。这里
n是级别数，在上述情况下为 4。
它的 space 复杂度为 O(n)。我确信可能有更好的解决方案，具有更好的 space 复杂性，但我无法想象它是否存在。有人有任何指示吗？
你不需要逐级存储节点，你可以通过将所有节点存储在一个deque structure中来解决任务，并在数组中维护节点的级别。
Deque <Integer> deque = new LinkedList();
Queue <Integer> q = new LinkedList();
int[]level = new int[n];//we need to store the level of each node, n is number of node
q.add(0);//Adding the root node
while(!q.isEmpty()){
int node = q.deque();
for(int child : getNodeChildren(node)){
level[child] = level[node] + 1;//Keep track the level of child node
q.add(child);
deque.add(child);//Store the child node into the queue.
}
}
// Print output
boolean printHead = true;
while(!deque.isEmpty()){
if(printHead){
int node = deque.pollFirst();
print node;
//Check if we already printed every node in this current level,
//if yes, we need to switch to print from the end of the queue
if(!deque.isEmpty() && level[deque.getFirst()] != level[node]){
printHead = false;
}
}else{
int node = deque.pollLast();
print node;
if(!deque.isEmpty() && level[deque.getLast()] != level[node]){
printHead = true;
}
}
}
代码逻辑为：
我们从deque开始一直打印，如果下一个节点和上一个打印的节点不在同一层级，这也意味着我们刚刚打印了当前层级的所有元素，我们需要切换到从deque结尾开始打印，反之亦然。我们继续这个过程，直到所有节点都被打印出来。
Space复杂度为O(n)，时间复杂度为O(n)。
首先我要感谢发帖人提出的问题，并提供一个时间复杂度和 space 复杂度如何相互对立的实际例子。给定大量 space，您的算法可以非常快（因为您可以创建 'state'）。相反，如果你在 space 中非常受限，你会发现有必要执行额外的迭代来弥补状态的不足。
事实证明，这个问题在space复杂度O(n)下很容易解决。如果您被允许为结果 (O(n)) 创建 space，则有几种算法可以创建时间复杂度 O(n) 的解决方案。发布了一个解决方案（我喜欢），我还提供了一种不同的、也许是优雅的方法来解决 O(n) 和时间复杂度 O(n)；参考方法solveOrderN().
挑战在于如何在小于 O(n) 的 space 复杂度中找到解决方案。为此，不得允许您创建结果 space，因此您被迫在问题中给出的树 space 内操作。你被迫交换元素。
我提供的解决方案——solveSubOrderN()——没有产生任何结果space；答案在与问题相同的内存 space 中返回。
我非常乐观地认为我可以在 O(log base 2(n)) 甚至接近 O(n) 的时间复杂度内解决这个问题。但是经过多方分析，我不能这么激进。
当你开始交换元素时，当你绕回 non-processable 元素时，你最终会碰到一个 'halting condition'。如果这个暂停不存在，你可以达到 O(log base 2 n)。但是你无法避免它。因此，为了弥补这一点，我不得不创建一些 space（布尔数组）来表示正在处理的元素的状态。
我想讨论这个布尔状态与为 result/solution 创建 space 有何不同。当您创建解决方案（n 个元素，大小为 s）时，您正在创建 space=n*s。在这个问题中，s 是一个整数。通常 s 可能非常大，这使它成为一个 'expensive'' 过程（也是发帖人造成此问题的原因）。布尔数组的 space 相当少，随着 s 大小的增长甚至可以忽略不计（即 n/s 随着 s 的增长接近 0）。
事实证明，当 space 复杂度小于 O(n) 时，您无法实现时间复杂度 O(n)。当您遇到停止条件时，您将被迫再次迭代。但事实证明，对于一棵二叉树来说，额外的迭代次数很少（而且每次迭代都是为了简单地找到下一个起点）。
所以综上所述，请找到以下两个解决方案；一个具有 space 复杂度 O(n) 和时间复杂度 O(n)，但更重要的是一个 space 复杂度低于 O(n)，时间复杂度非常接近 O(n ).
public class BinaryTree {
public static void main(String[] args) {
int treeN2[] = {1, 2, 3};
int treeN3[] = {1, 2, 3, 4, 5, 6, 7};
int treeN4[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
int treeN5[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31};
int answer[] = solveOrderN(treeN5);
System.out.println(Arrays.toString(answer));
solveSubOrderN(treeN5);
System.out.println(Arrays.toString(treeN5));
}
/**
* Given a binary tree, Perform inward spiral tree traversal.<br>
* With this approach, there is no space created for the result.
* All manipulation is done within the original tree<br>
* Some space is created (boolean[n]) to add necessary state of processing.
* Space Complexity: Less than O(n), greater than log(base2)(n)
* Time Complexity: Slightly greater than O(n)
* @param tree Input tree
*/
public static void solveSubOrderN(int tree[]) {
boolean complete[] = new boolean[tree.length];
Arrays.fill(complete, false);
System.out.println("Solving Sub O(n); tree size="+tree.length);
int n = log2Round(tree.length+1);
if (n == 1)
return;
int o[] = getLevelOffsets(n);
System.out.println("Number of levels="+n);
int pos = 0;
complete[0] = true;
int currentValue = 0;
int moves=1;
while (moves < tree.length) {
pos = getStartingPos(complete);
currentValue = tree[pos];
tree[pos] = 0;
while (true) {
int nextPos = getTargetPosition(pos, o, n);
int nextValue = tree[nextPos];
tree[nextPos] = currentValue;
complete[nextPos] = true;
currentValue = nextValue;
pos = nextPos;
moves++;
if (currentValue == 0)
break;
}
}
}
/**
* Given a binary tree, Perform inward spiral tree traversal.
* Space Complexity: O(n)
* Time Complexity: O(n)
* @param tree Input tree
* @return The solution
*/
public static int[] solveOrderN(int tree[]) {
int answer[] = new int[tree.length];
int n = log2Round(tree.length+1);
int o[] = getLevelOffsets(n);
System.out.println("Solving O(n); tree size="+tree.length);
System.out.println("Number of levels="+n);
for (int i = 0; i < tree.length; i++) {
answer[getTargetPosition(i, o, n)] = tree[i];
}
return answer;
}
/**
* Search for the first unprocessed element
* @param complete An array of boolean (true = processed)
* @return
*/
public static int getStartingPos(boolean[] complete) {
for (int i=0; i<complete.length; i++) {
if (!complete[i])
return i;
}
return 1;
}
public static int getTargetPosition(int pos, int o[], int n) {
int row = getRow(pos);
int rowOrder = getRowOrder(row, n);
boolean isReversed = isBottom(row, n);
int posInRow = getPosInRow(pos, n);
int rowOffset = getRowOffset(rowSize(row), posInRow, isReversed);
return o[rowOrder]+rowOffset;
}
public static int getRowOffset(int rowSize, int posInRow, boolean isReversed) {
if (!isReversed)
return posInRow;
else
return rowSize-posInRow-1;
}
public static int rowSize(int row) {
return exp(row, 2);
}
public static int getPosInRow(int pos, int n) {
int row = getRow(pos);
return pos-(exp(row,2)-1);
}
/**
* The top n/2 rows print forward, the bottom n/2 rows print reversed
* @param row Zero based row [0 to n-1]
* @param n Number of levels to the tree
* @return true if line should be printed forward, false if reversed
*/
public static boolean isBottom(int row, int n) {
int halfRounded = n/2;
return (row <= n-halfRounded-1) ? false : true;
}
public static int exp(int n, int pow) {
return (int)Math.pow(pow, n);
}
public static double log2(int n) {
return (Math.log(n) / Math.log(2));
}
public static int log2Round(int n) {
return (int)log2(n);
}
/**
* For a given position [0 to N-1], find the level on the binary tree [0 to n-1]
* @param pos Zero based position in the tree (0 to N-1)
* @return Zero based level (0 to n-1)
*/
public static int getRow(int pos) {
return log2Round(pos+1);
}
/**
* For a given row [0 to n-1], find the order in which that line would be processed [1 to log base 2 n]
* @param row The row in the tree [0 to n-1]
* @return The order that row would be processed [0 to n-1]
*/
public static int getRowOrder(int row, int n) {
return isBottom(row, n) ? (n-row-1)*2+1 : row*2;
}
public static int getRowForOffset(int row, int n) {
boolean isOdd = row%2 == 1;
return isOdd ? n-(row-1)/2 - 1 : row/2;
}
/**
* Compute the offset for a given ordered row
* @param n The number of levels in the tree
* @return Generated offsets for each row (to keep time complexity at O(n))
*/
public static int[] getLevelOffsets(int n) {
int o[] = new int[n];
Arrays.fill(o, 0);
o[0] = 0;
int offset = 0;
for (int i=0; i<n; i++) {
int nextRow = getRowForOffset(i, n);
o[i] = offset;
offset += exp(nextRow, 2);
}
return o;
}
}
这是一个用O(1)space和O(n * h)时间的简单解决方案，其中n是节点数，h是树高。保留两个指向当前层次的变量进行打印，然后根据长度对应合适的树深度的二进制字符串遍历树后打印每个节点；向左走“0”，向右走“1”（例如，示例中的 left-most 节点由“000”到达，其邻居位于“001”）。由于要打印一个节点，我们最多需要进行 h 次迭代，时间复杂度为 O(n * h).
下面是稍微详细一点的算法：
down = 0
up = tree height
while:
if down > up:
break
else:
set exp to down then up (or only one if up == down):
for i = 0 to 2^exp - 1:
s = binary string i, padded to exp digits
traverse tree according to s
if a node exists by the end of s:
print node
down = down + 1
up = up - 1
我不确定它是否会快一个数量级，但您可以使用相同的原则在树中行走，而不是从每个节点的根开始：返回直到“0”遇到，将其翻转为“1”，然后一直向左保持下降到目标层级，递归重复，直到字符串全为“1”。例如，目标级别 4：
0000 => (000)1 => (00)10 => (001)1 => (0)100...etc.
你可以在没有明显额外的情况下解决它 space，但它需要 O(n)。时间复杂度取决于二叉树的表示。 如果你有一个数组，时间复杂度将是 O(n)，例如：
public static void main(String[] args) {
int[] binaryTree = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
int nodes = binaryTree.length;
int levels = (int) Math.ceil(Math.log(nodes) / Math.log(2));
int[] increment = {1, -1};
int index = 0;
for (int i = 0; i < levels; i++) {
int level = (index) * levels + increment[index] * (i / 2) - index;
int begin = (int) Math.round(Math.pow(2, level));
int[] range = {begin, 2 * begin - 1};
for (int j = range[index]; j != range[1 - index]; j += increment[index]) {
System.out.print(" " + binaryTree[j-1]);
}
System.out.print(" " + binaryTree[range[1 - index]-1]);
index = 1 - index;
}
System.out.println();
}
如果您有一个二叉树，其节点定义为：
publi class Node {
Node[] children;
int value;
}
时间复杂度（没有额外的 space）将为 O(n*log(n))。 示例：
public class BinaryNode {
BinaryNode[] children = {null, null};
int value;
public BinaryNode(int value) {
this.value = value;
}
private int getRecursive(int reference) {
int result = value;
if (reference > 1) {
result = children[reference%2].getRecursive(reference/2);
}
return result;
}
public int get(int p) {
int reference = 1;
int p2 = p;
while (p2 > 1){
reference = (reference << 1) + (p2 & 1);
p2 >>= 1;
}
return getRecursive(reference);
}
private void generateLevels(int levels){
if (levels > 0){
children[0] = new BinaryNode(value*2);
children[0].generateLevel(levels -1);
children[1] = new BinaryNode(value*2+1);
children[1].generateLevel(levels -1);
}
}
public static BinaryNode generate(int levels){
BinaryNode result = null;
if (levels > 0){
result = new BinaryNode(1);
result.generateLevels(levels - 1);
}
return result;
}
public static void main(String[] args) {
int levels = 5;
BinaryNode btreeRoot = BinaryNode.generate(levels);
int[] increment = {1, -1};
int index = 0;
for (int i = 0; i < levels; i++) {
int level = (index) * levels + increment[index] * (i / 2) - index;
int begin = (int) Math.round(Math.pow(2, level));
int[] range = {begin, 2 * begin - 1};
for (int j = range[index]; j != range[1 - index]; j += increment[index]) {
System.out.print(" " + btreeRoot.get(j));
}
System.out.print(" " + btreeRoot.get(range[1 - index]));
index = 1 - index;
}
System.out.println();
}
}
编辑
如何用 n 计算 h？ 简单：
h = log2(n)
因此，时间复杂度：O(n * log n) == O(n * h)。
算法在O(log(n))中获取一个元素，需要获取所有(n个元素)所以，结果时间复杂度为O(n * log(n))。 该算法无需额外 space.
BtreeRoot为原始二叉树，算法按正确顺序获取所有节点，计算level中的下一层。 level 在 O(1)（log2(n) 次）中转到值 (1, levels -1, 2, levels - 2)
在每一层中，算法获得其m个节点：从2^level到2^(level +1) - 1。所有级别的总和为n（节点数），
根据级别（奇数或对数），从头到尾或反向计算当前节点位置。那么就知道当前节点要打印的位置，需要取值，在完美二叉树中，需要Log(n)。
通过说您的 space 复杂度 < O(n)，您似乎在假设树的表示方式，然后您无法使用任何其他数据来扩充该表示and/or 解决方案中的结构（即 O(n)）。
对于我的回答，我将假设树是完整的（或至少是平衡的），其中平衡意味着树的高度是 O(logN)。
在此假设下，我们可以将树存储在堆数据结构中。在这个结构中，节点数据存储在一个数组中，其中，层级排列：
[0][1][1][2][2][2][2][3][3][3][3][3][3][3][3]...
如果树中不存在该节点，则数组中的给定位置将具有指向节点数据的指针或指向 NULL 的指针。
本例中 space 的数量是 O(2^L)，其中 L 是树中的层数。在平衡树中，L = O(log(N))，所以这个表示的大小是O(N).
同样假设我们知道这个数组的大小，那么树的层数是ceiling(log_2(size)).
假设 Levels 从 0...K-1 开始，数组中任何级别的起始位置为：2^L - 1.
这是算法的伪代码。
PrintLevel( Array<Node> heap, level) {
int levelStart = power( 2, level ) - 1;
int nextLevelStart = (levelStart + 1) * 2 - 1; // same as power( 2, level+1 ) - 1
for( int i = levelStart; i < nextLevelStart; i++ ) {
if( heap[i] != NULL ) {
print( heap[i] );
}
}
}
SpiralPrint( Array<Node> heap ) {
int lowLevel = Ceil(Log(heap.size())) - 1
int highLevel = 0
while( lowLevel >= highLevel ){
PrintLevel( heap, highLevel );
if (lowLevel > highLevel)
PrintLevel( heap, lowLevel );
highLevel += 1;
lowLevel -= 1;
}
}