题目

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”] 需要得到所有从根到叶子结点的路径。

解题思路

既然是得到路径，那么很自然的想到使用深度优先遍历（DFS），DFS在二叉树中对应的就是前序遍历，然后用一个ArrayList保存访问过的节点，就可以了。

public class leetcode257 { private ArrayList<Integer> record = new ArrayList<>(); private List<String> res = new ArrayList<>(); public List<String> binaryTreePaths(TreeNode root) { helper(root); return res; } private void helper(TreeNode node) { if (node != null) { //节点加入记录 record.add(node.val); helper(node.left); helper(node.right); if (node.left == null && node.right == null) { //叶子结点，打印输出记录里所有节点. String temp = ""; for (int i = 0; i < record.size(); i++) { if (i == 0) temp += record.get(i); else temp = temp + "->" + record.get(i); } res.add(temp); } //此时，该节点左右子树都已经打印输出完毕，可以从记录中删除 record.remove(record.size() - 1); } } }