打印二叉树所有的路径

谁践踏了优雅 2022-09-26 02:20 113阅读 0赞

问题：

给一个二叉树，把所有的路径都打印出来。

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

8 -> 3 -> 1

8 -> 2 -> 6 -> 4

8 -> 3 -> 6 -> 7

8 -> 10 -> 14 -> 13

![0_1323544109n86f.gif][]

思路：

从根节点开始，把自己的值放在一个数组里，然后把这个数组传给它的子节点，子节点同样把自己的值放在这个数组里，又传给自己的子节点，**直到这个节点是叶节点**，然后把这个数组打印出来。所以，我们这里要用到递归。

代码：

**\[java\]**  [view plain][]   [copy][view plain]

1.  /\*\* 
2.  Given a binary tree, prints out all of its root-to-leaf 
3.  paths, one per line. Uses a recursive helper to do the work. 
4.  \*/  
5.  **public** **void** printPaths(Node root, **int** n) \{  
6.      String\[\] path = **new** String\[n\];  
7.      printPaths(root, path, 0);  
8.  \}  
9.  /\*\* 
10. Recursive printPaths helper -- given a node, and an array containing 
11. the path from the root node up to but not including this node, 
12. prints out all the root-leaf paths. 
13. \*/  
14. **private** **void** printPaths(Node node, String\[\] path, **int** pathLen) \{  
15.     **if** (node == **null**) **return**;  
16.     // append this node to the path array  
17.         path\[pathLen++\] = node.value;  
18.     // it's a leaf, so print the path that led to here  
19.     **if** (node.leftChild == **null** && node.rightChild == **null**) \{  
20.         printArray(path, pathLen);  
21.     \}  
22.     **else** \{  
23.         // otherwise try both subtrees  
24.         printPaths(node.leftChild, path, pathLen);  
25.         printPaths(node.rightChild, path, pathLen);  
26.     \}  
27. \}  
28. /\*\* 
29. Utility that prints strings from an array on one line. 
30. \*/  
31. **private** **void** printArray(String\[\] ints, **int** len) \{  
32.     **for** (**int** i = 0; i < len; i++) \{  
33.         System.out.print(ints\[i\] + " ");  
34.     \}  
35.     System.out.println();  
36. \}

备注：这里只能用一个数组+一个数值才能打印出所需要的路径，如果用linkedlist之类的链表结构是不行的。值得分析一下原因，很有意思。

[0_1323544109n86f.gif]: /images/20220717/855599dda6e04112875b2da7788843f7.png
[view plain]: http://blog.csdn.net/beiyeqingteng/article/details/7060642#