算法 - 如何不用递归 列出 树（多叉） 中根节点到叶节点的所有路径（Java）

Question

比如，对于下面这个二叉树，它所有的路径为：

8 -> 3 -> 1

8 -> 2 -> 6 -> 4

8 -> 3 -> 6 -> 7

8 -> 10 -> 14 -> 13

怎么用Java去实现？

Answer 1

If you don’t need recursion, then use depth first!
Use the stack, first push the root node into the stack, if the stack is not empty, then pop it out and output the median value of the current node, then push the right subtree onto the stack first, then push the left subtree onto the stack, and then Determine whether the stack is empty, loop... The steps are as follows:
1) First push the root node of the binary tree into the stack
2) Determine whether the stack is empty, if not, pop it out of the stack and output the pop tree The value of the node
3) The right subtree of the pop tree node is pushed onto the stack
4) The left subtree of the pop tree node is pushed onto the stack
5) Loop back to (2)
This is the one I saw before Method, I wonder if it can help the questioner?

public void depthOrderTraversal(){  
        if(root==null){  
            System.out.println("empty tree");  
            return;  
        }         
        ArrayDeque<TreeNode> stack=new ArrayDeque<TreeNode>();  
        stack.push(root);         
        while(stack.isEmpty()==false){  
            TreeNode node=stack.pop();  
            System.out.print(node.value+"    ");  
            if(node.right!=null){  
                stack.push(node.right);  
            }  
            if(node.left!=null){  
                stack.push(node.left);  
            }             
        }  
        System.out.print("\n");  
    }  

Answer 2

Replace recursion with stack: https://zh.coursera.org/learn...

Answer 3

Depth first? . .

Answer 4

Use breadth-first traversal, then store all the parent nodes of the node in the state, and output them after reaching the leaf node.