打印树中从根到每个叶子的所有路径

Question

我正在尝试打印树中从根到叶的所有路径，但在收集路径项时遇到了一些问题。

考虑下图：

但在我的例子中，结果如下：

10 -> 8 -> 3 -> 
10 -> 8 -> 3 -> 5 -> 
10 -> 8 -> 3 -> 5 -> 2 -> 2 ->

所以每条路径都有来自先前节点的值。我就是这样做的：

class TreeNode(val n: Int, val children: MutableList<TreeNode> = mutableListOf())

fun main() {
    val root = TreeNode(10)
    val eight = TreeNode(8)
    val three = TreeNode(3)
    val five = TreeNode(5)
    val two = TreeNode(2)
    val twotwo = TreeNode(2)

    root.children.add(eight)
    root.children.add(two)
    eight.children.add(three)
    eight.children.add(five)
    two.children.add(twotwo)

    printTree(root, mutableListOf(), 0)
}

fun printTree(root: TreeNode, list: MutableList<Int>, index: Int) {
    list.add(root.n)

    if (root.children.isEmpty()) {
        list.forEach {
            print("$it -> ")
        }
        println()
    } else {
        root.children.forEach {
            printTree(it, list, index + 1)
        }
    }
}

我知道这个问题源于我将项目存储在同一个列表 MutableList<Int> 中，该列表与每个递归调用共享。有什么想法可以调整实施以产生预期的结果吗？

Answer 1

您需要在退出递归方法之前删除节点（如评论中所建议）。实施：

fun printTree(root: TreeNode, list: MutableList<TreeNode>) {
    list.add(root)
    root.children.forEach {
        printTree(it, list)
    }
    if (root.children.isEmpty())
        println(list.joinToString(" -> ") { it.n.toString() })
    list.removeLast()
}

Try it yourself

Answer 2

data class Node(
  val value: Int,
  val children: List<Node>? = null
)

val tree =
  Node(
    10, listOf(
      Node(
        8, listOf(
          Node(3), Node(5)
        )
      ),
      Node(
        2, listOf(
          Node(2)
        )
      )
    )
  )

// Create a list of lists, each list containing the nodes of a path
fun getAllPaths(node: Node): List<List<Node>> {
  return if (node.children.isNullOrEmpty()) {
    listOf(listOf(node))
  } else {
    node.children.flatMap { child -> getAllPaths(child) }.map { nodes -> listOf(node) + nodes }
  }
}

val paths = getAllPaths(tree)

// Print the values
paths.forEach { path -> println(path.joinToString(" -> ") { node -> node.value.toString() }) }
// 10 -> 8 -> 3
// 10 -> 8 -> 5
// 10 -> 2 -> 2

// Or alternatively extract the values from the nodes
val values = paths.map { nodes -> nodes.map { node -> node.value } }
values.forEach(::println)
// [10, 8, 3]
// [10, 8, 5]
// [10, 2, 2]

Answer 3

这个 java 代码就是您所需要的！

public class BinaryTreePrintAllPaths {
 
    public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }
 
    // Prints all paths to leaf
    public static void printAllPathsToLeaf(TreeNode node, int[] path, int len) {
        if ( node == null )
            return;
 
        // storing data in array
        path[len] = node.data;
        len++;
 
        if(node.left == null && node.right == null) {
            // leaf node is reached
            printArray(path,len);
            return;
        }
 
        printAllPathsToLeaf(node.left, path, len);
        printAllPathsToLeaf(node.right, path, len);
    }
 
    public static void main(String[] args)
    {
        // Creating a binary tree
        TreeNode rootNode=createBinaryTree();
        System.out.println("Printing all paths from root to leaf :");
        printAllPathsToLeaf(rootNode,new int[1000],0);
    }
 
    public static void  printArray(int[] path,int len)
    {
        for (int i = 0; i < len; i++) {
            System.out.print(" "+path[i]);
        }
        System.out.println();
    }
    
    
    public static TreeNode createBinaryTree()
    {
 
        // you can implement add method more elegant,I just did in this way to answer quickly
        
        TreeNode rootNode =new TreeNode(10);
        TreeNode node8=new TreeNode(8);
        TreeNode node3=new TreeNode(3);
        TreeNode node5=new TreeNode(5);
        TreeNode node2=new TreeNode(2);
        TreeNode node2_2=new TreeNode(2);
 
        rootNode.left=node8;
        rootNode.right=node2;
 
        node8.left=node3;
        node8.right=node5;
 
        node2.left=node2_2;
       
        return rootNode;
    }
}

打印树中从根到每个叶子的所有路径

Printing all the paths in a tree from root to each leaf

java

algorithm

tree

data-structures

kotlin