如何在不使用递归的情况下打印树的每个叶路径。
这是一棵树，不是二叉树。
struct node {
int data
std::vector<node*> children;
}
-------------root ------d m n ---x y z o p结果应为:
root-d-x root-d-y root-d-z root-m root-n-o root-n-p我试图使用非递归方法但失败了。
public static void printAllPathToLeafNonRecursive(Node root) {
if (root == null) {
return;
}
Queue<Object> q = new LinkedList<Object>();
q.add(root);
q.add(root.data + "");
while(!q.isEmpty()){
Node head = (Node) q.poll();
String headPath = (String) q.poll();
if(head.isLeaf()){
System.out.println(headPath);
continue;
}
if(head.left!=null){
String leftStr = headPath + "->" + head.left.data;
q.add(head.left);
q.add(leftStr);
}
if(head.right!=null){
String rightStr = headPath + "->" + head.right.data;
q.add(head.right);
q.add(rightStr);
}
}
}
class Stack(object): # just for reference
def __init__(self):
self.a = []
def push(self, b):
self.a.append(b)
def peek(self):
return self.a[-1]
def pop(self):
return self.a.pop()
def isEmpty(self):
return len(self.a) == 0
def show(self):
return self.a
def paths(troot): # you should create your own Tree and supply the root
current = troot
s = Stack()
s.push(current)
s.push(str(current.key))
s.push(current.key)
while not s.isEmpty():
pathsum = s.pop()
path = s.pop()
current = s.pop()
if not current.left and not current.right:
print 'path: %s, pathsum: %d' % (path, pathsum)
if current.right:
rightstr = path + "->" + str(current.right.key)
rightpathsum = pathsum * 10 + current.right.key
s.push(current.right)
s.push(rightstr)
s.push(rightpathsum)
if current.left:
leftstr = path + "->" + str(current.left.key)
leftpathsum = pathsum * 10 + current.left.key
s.push(current.left)
s.push(leftstr)
s.push(leftpathsum)
For example, for the following tree:
3
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
1 7
/ \ / \
/ \ / \
/ \ / \
/ \ / \
0 2 5 8
/ \ / \ / \ / \
/ \ / \ / \ / \
NUL NUL NUL NUL 4 6 NUL 9
>>> paths()
path: 3->1->0, pathsum: 310
path: 3->1->2, pathsum: 312
path: 3->7->5->4, pathsum: 3754
path: 3->7->5->6, pathsum: 3756
path: 3->7->8->9, pathsum: 3789
这个策略很简单。向下走，然后向右，最后向上。在每个点上，你都知道下一步该去哪里。
保持一个向量，表示你在树中的当前位置。将其起始点设置为根节点。然后用伪代码表示如下：
while True:
if not a leaf:
current_place.push_back(0) // move down one
else:
print current path.
while can't move right:
if at root:
exit()
current_place.pop_back() //move up one
current_place[-1] += 1
这些操作将需要函数调用。但它们是循环的函数调用，不是递归的，因此它不是递归。
public static void RoottoPathPrint(BinaryTreeNode root) {
Stack<Object> stack = new Stack<Object>();
if (root == null)
return;
stack.push(root.getData() + "");
stack.push(root);
while (!stack.isEmpty()) {
BinaryTreeNode temp = (BinaryTreeNode) stack.pop();
String path = (String) stack.pop();
if (temp.getRight() != null) {
stack.push(path + temp.getRight().getData());
stack.push(temp.getRight());
}
if (temp.getLeft() != null) {
stack.push(path + temp.getLeft().getData());
stack.push(temp.getLeft());
}
if (temp.getLeft() == null && temp.getRight() == null) {
System.out.println(path);
}
}
}
这个想法是在遍历树时将路径和节点都记录在单个堆栈中。对象堆栈可以实现此操作。 希望这有所帮助！！
private void rootToLeaf(BSTNode root){
Stack<Map<BSTNode,ArrayList<Integer>>> tmpStack = new Stack<Map<BSTNode,ArrayList<Integer>>>();
Map<BSTNode,ArrayList<Integer>> tmpMap = new HashMap<BSTNode,ArrayList<Integer>>();
//List<Integer> tmp_arraylist = new ArrayList<Integer>();
ArrayList<Integer> tmpList = new ArrayList<Integer>();
tmpList.add(root.data);
tmpMap.put(root, tmpList);
tmpStack.push(tmpMap);
while(!tmpStack.isEmpty()){
Map<BSTNode,ArrayList<Integer>> temp_map = tmpStack.pop();
for(BSTNode node : temp_map.keySet()){
if(node.getLeft()==null && node.getRight()==null){
for(int i: temp_map.get(node)){
System.out.print(i+" ");
}
System.out.println();
}
if(node.getRight()!=null){
ArrayList<Integer> tmp_List = new ArrayList<Integer>();
for(int i: temp_map.get(node)){
tmp_List.add(i);
}
tmp_List.add(node.getRight().getData());
Map<BSTNode,ArrayList<Integer>> tmphashMap = new HashMap<BSTNode,ArrayList<Integer>>();
tmphashMap.put(node.getRight(), tmp_List);
tmpStack.push(tmphashMap);
}
if(node.getLeft()!=null){
ArrayList<Integer> tmp_List = new ArrayList<Integer>();
for(int i: temp_map.get(node)){
tmp_List.add(i);
}
tmp_List.add(node.getLeft().getData());
Map<BSTNode,ArrayList<Integer>> tmphashMap = new HashMap<BSTNode,ArrayList<Integer>>();
tmphashMap.put(node.getLeft(), tmp_List);
tmpStack.push(tmphashMap);
}
}
}
}
public void allPathsToLeafNodesWithPreOrderDFS() {
Stack<Node> stack = new Stack<> ();
stack.push (root);
List<Deque<Integer>> paths = new ArrayList<> ();
while (!stack.isEmpty ()) {
Node pop = stack.pop ();
System.out.print (" " + pop.data);
if (pop.isLeaf ()) {
Deque<Integer> path = new ArrayDeque<> ();
Node current = pop;
while (current != null) {
path.add (current.data);
current = current.parent;
}
paths.add (path);
}
if (pop.right != null) {
pop.right.parent = pop;
stack.push (pop.right);
}
if (pop.left != null) {
pop.left.parent = pop;
stack.push (pop.left);
}
}
System.out.println ("paths = " + paths);
}
public void allPathsToLeafNodesWithInOrderDFS() {
Stack<Node> stack = new Stack<> ();
List<Deque<Integer>> paths = new ArrayList<> ();
Node current = root;
while (!stack.isEmpty () || current != null) {
if (current != null) {
stack.push (current);
if (current.left != null) current.left.parent = current;
current = current.left;
} else {
Node pop = stack.pop ();
System.out.println (" " + pop.data);
if (pop.isLeaf ()) {
Deque<Integer> path = new ArrayDeque<> ();
Node now = pop;
while (now != null) {
path.add (now.data);
now = now.parent;
}
paths.add (path);
}
current = pop.right;
if (pop.right != null) pop.right.parent = pop;
}
}
System.out.println ("paths = " + paths);
}
public void allPathsToLeafNodesWithBFS (){
List<Deque<Integer>> paths = new ArrayList<> ();
Queue<Node> queue = new LinkedList<> ();
queue.add (root);
while (!queue.isEmpty ()){
Node poll = queue.poll ();
System.out.println ("poll = " + poll);
if (poll.isLeaf ()){
Deque<Integer> path = new ArrayDeque<> ();
Node current = poll;
while (current != null){
path.add (current.data);
current = current.parent;
}
paths.add (path);
}
if(poll.left != null) {
poll.left.parent = poll;
queue.add (poll.left);
}
if(poll.right != null) {
poll.right.parent = poll;
queue.add (poll.right);
}
}
System.out.println ("paths = " + paths);
}
100
/ / \ \
1 2 3 4
/ / / / / / \
10 11 12 13 14 40 41
/ \
400 401
public void traverseDFS(Node root) {
Stack<Node> s = new Stack<Node>();
Stack<String> sPath = new Stack<>();
Stack<Integer> sSum = new Stack<>();
s.push(root); sPath.push(root.Id + ""); sSum.push(root.Id);
while (!s.isEmpty()) {
// Pop out
Node head = s.pop(); String headPath = sPath.pop(); Integer headSum = sSum.pop();
if(head.children == null || head.children.isEmpty()){ //Leaf
System.out.println(headPath + "(" + headSum+")");
continue;
}
for(Node child : head.children) {
String path = headPath + "->" + child.Id;
Integer sum = headSum + child.Id;
// Push on stack
s.push(child); sPath.push(path); sSum.push(sum);
}
}
}
public static void traverseBFS(Node root) {
Queue<Node> q = new LinkedList<>();
Queue<String> qPath = new LinkedList<>();
Queue<Integer> qSum = new LinkedList<>();
q.add(root); qPath.add(root.Id + ""); qSum.add(root.Id);
while(!q.isEmpty()){
// Poll the q
Node head = q.poll(); String headPath = qPath.poll(); Integer headSum = qSum.poll();
if(head.children == null || head.children.isEmpty()){ //Leaf
System.out.println(headPath + "(" + headSum+")");
continue;
}
for(Node child : head.children) {
String path = headPath + "->" + child.Id;
Integer sum = headSum + child.Id;
// Add to the q
q.add(child); qPath.add(path); qSum.add(sum);
}
}
}
class Node {
int Id;
String Data;
Node Parent;
ArrayList<Node> children;
public Node(int id, String data) {
Id = id;
Data = data;
}
}
输出
-----------Depth FS-------------
100->4->41(145)
100->4->40->401(545)
100->4->40->400(544)
100->3(103)
100->2(102)
100->1->14(115)
100->1->13(114)
100->1->12(113)
100->1->11(112)
100->1->10(111)
-----------BFS-------------
100->2(102)
100->3(103)
100->1->10(111)
100->1->11(112)
100->1->12(113)
100->1->13(114)
100->1->14(115)
100->4->41(145)
100->4->40->400(544)
100->4->40->401(545)
node中添加一个父节点指针，以达到最小内存开销。请参考非递归中序遍历。 - Alexey Frunze