Binary Tree Paths

輸出二叉樹的尋葉路徑

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1

 /   \

2    3

  \

   5

All root-to-leaf paths are:

["1->2->5", "1->3"]

周遊二叉樹的時候，每當尋到葉結點，把路徑裝進結果裡

1 package com.rust.datastruct;
 2 
 3 import java.util.ArrayList;
 4 import java.util.List;
 5 
 6 /**
 7  * judging
 8  * Binary Tree Paths
 9  *
10  * Given a binary tree, return all root-to-leaf paths.
11  *
12  * For example, given the following binary tree:
13  *
14  *   1
15  * /   \
16  * 2    3
17  * \
18  * 5
19  * All root-to-leaf paths are:
20  * ["1->2->5", "1->3"]
21  */
22 class BinaryTreePathsSolution {
23     List<String> res = new ArrayList<String>();
24     public List<String> binaryTreePaths(TreeNode root) {
25         if (root != null) track(root, root.val + "");/* String.valueOf(root.val)*/
26         return res;
27     }
28     private void track(TreeNode n, String path){
29         if (n.left == null && n.right == null) res.add(path);
30         if (n.left != null) track(n.left, path + "->" + n.left.val);/* continue tracking */
31         if (n.right != null) track(n.right, path + "->" + n.right.val);
32     }
33 }
34 
35 /**
36  * Test main
37  */
38 public class BinaryTreePaths {
39     public static void main(String args[]) {
40         TreeNode root = new TreeNode(0);
41         TreeNode node1 = new TreeNode(1);
42         TreeNode node2 = new TreeNode(2);
43         TreeNode node3 = new TreeNode(3);
44         TreeNode node4 = new TreeNode(4);
45         TreeNode node5 = new TreeNode(5);
46         TreeNode node6 = new TreeNode(6);
47         TreeNode node7 = new TreeNode(7);
48 
49         root.left = node1;
50         root.right = node2;
51         node1.left = node3;
52         node1.right = node4;
53         node2.left = node5;
54         node2.right = node6;
55         node4.right = node7;
56 
57         BinaryTreePathsSolution solution = new BinaryTreePathsSolution();
58         List<String> res = solution.binaryTreePaths(root);
59 
60         for (int i = 0;i < res.size();i++){
61             System.out.print(res.get(i) + " ");
62         }
63         System.exit(0);
64     }
65 
66 }      

輸出：

0->1->3 0->1->4->7 0->2->5 0->2->6