Considering a N-ary tree with this node structure:

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

}

And we want to convert the tree to NodeTypeB tree, but the internal structure of NodeTypeB is invisible, and we can only construct the new tree using two method:

//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);

The recursive solution is trivial, how can we do it in non-recursive way?

Recursive solution

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

}

CodePudding user response：

You can use a stack for this. A stacked element should have a reference to a NodeTypeA instance, and to a list of NodeTypeB instances. As long as the size of that list is smaller than the number of children of the NodeTypeA node, the stack should be extended with the next child of NodeTypeA that has not yet been mapped. When a node can be mapped, it is appended to the list of NodeTypeB instances at the top of the stack, and the process continues with the next child (if any).

When the number of children is equal, then all has been done for the stacked NodeTypeA instance, and all is available to create an internal NodeTypeB node. This item can then be popped from the stack, and the created node can be appended to the list that is now on the top of the stack.

This continues until the stack is empty.

As implementation, you could first define this simple class:

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

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

And then the convert function could look like this:

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);
        }
    }
}

CodePudding user response：

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


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


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

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