自底向上转换 N 叉树，无需递归

Question

考虑具有这种节点结构的N叉树：

class NodeTypeA {
  String payload;
  List<NodeTypeA> children;

}

并且我们希望将树转换为NodeTypeB树，但是NodeTypeB的内部结构是不可见的，我们只能构造新树使用两种方法：

//This method can only convert leaf NodeTypeA (no children)
public NodeTypeB convertLeaf(NodeTypeA nodeTypeA);

//This method can convert a non-leaf NodeTypeA as long as its children are converted
public NodeTypeB convertParent(NodeTypeA parentNodeTypeA, List<NodeTypeB> nodeTypeBs);

递归解决方案很简单，我们如何以非递归方式做到这一点？

递归解法

public NodeTypeB convert(NodeTypeA root) {
  if(root == null) return null;
  
  if(root.children == null || root.children.size() == 0) {
  return convertLeaf(root);
  }  
 
  List<NodeTypeB> nodeBs = new ArrayList<>();
  for(NodeTypeA child：root.children) {
      nodeBs.add(convert(child));
  }
  return convertParent(root, nodeBs);

}

Answer 1

您可以为此使用堆栈。堆叠元素应该具有对 NodeTypeA 实例和 NodeTypeB 实例列表的引用。只要该列表的大小小于 NodeTypeA 节点的子节点数量，堆栈就应该使用尚未扩展的 NodeTypeA 的下一个子节点进行扩展。映射。当一个节点可以被映射时，它将被附加到堆栈顶部的 NodeTypeB 实例列表中，并且该过程继续处理下一个子节点（如果有）。

当子级数量相等时，堆叠的 NodeTypeA 实例的所有操作都已完成，并且所有操作都可用于创建内部 NodeTypeB 节点。然后可以从堆栈中弹出该项目，并且可以将创建的节点追加到现在位于堆栈顶部的列表中。

这一直持续到堆栈为空为止。

作为实现，您可以首先定义这个简单的类：

public class NodeHybrid {
    NodeTypeA parentA;
    List<NodeTypeB> childrenB = new ArrayList<>();

    NodeHybrid(NodeTypeA parent) {
        parentA = parent;
    }
}

然后 convert 函数可能如下所示：

public NodeTypeB convert(NodeTypeA root) {
    if (root == null) return null;
    Stack<NodeHybrid> stack = new Stack<NodeHybrid>();
    stack.push(new NodeHybrid(root));
    while (true) {
        NodeHybrid node = stack.peek();
        if (node.parentA.children.size() > node.childrenB.size()) {
            stack.push(new NodeHybrid(node.parentA.children.get(node.childrenB.size())));
        } else {
            NodeTypeB converted = node.parentA.children.size() == 0
                ? convertLeaf(node.parentA)
                : convertParent(node.parentA, node.childrenB);
            stack.pop();
            if (stack.size() == 0) return converted;
            stack.peek().childrenB.add(converted);
        }
    }
}

Answer 2

# RLN traversal with backtracking
def itera(node):
    stack = node and [(node, [])]
    while stack:
        if stack[-1][0].children:
            stack.append((stack[-1][0].children.pop(), []))
            continue
        node = leaf(stack.pop()[0]) if stack[-1][0].children is None else parent(*stack.pop())
        if stack: stack[-1][1].append(node)
    return node


# test
from collections import namedtuple
Node = namedtuple("Node", "val children", defaults=[None])
leaf = lambda node: Node(node.val + 1000)
parent = lambda node, children: Node(node.val + 100, children)
recur = lambda node: node and (parent(node, list(map(recur, reversed(node.children)))) if node.children else leaf(node))
nodeA = Node(9, [Node(8, [Node(7, [Node(6), Node(5)])]), Node(4, [Node(3)]), Node(2, [Node(1), Node(0)])])
nodeB = Node(109, [Node(102, [Node(1000), Node(1001)]), Node(104, [Node(1003)]), Node(108, [Node(107, [Node(1005), Node(1006)])])])
assert recur(nodeA) == itera(nodeA) == nodeB


"""
nodeA
9
├── 8
│   └── 7
│       ├── 6
│       └── 5
├── 4
│   └── 3
└── 2
    ├── 1
    └── 0

nodeB
109
├── 102
│   ├── 1000
│   └── 1001
├── 104
│   └── 1003
└── 108
    └── 107
        ├── 1005
        └── 1006
"""