二叉树专题--输出根节点到所有叶子节点的路径

1.题目

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”]

2.解法

新建一个名为arrayListSingle的ArrayList，存放遍历过的路径，采用前序遍历的方式，每遍历一个子节点就将正在遍历的节点存入arrayListSingle，每当从子节点遍历返回时，例如上面题中给的例子里从5返回2时，就将arrayListSingle的最后一个元素，也就是刚遍历过的子节点删除，当发现正在遍历的节点没有子节点的时候，就说明走到了叶子节点位置，arrayListSingle里存的就正好是一条从根节点到该叶子的路径，这时就将arrayListSingle里的路径以String形式存到最终结果List里。具体代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        // 存放最终的所有从根到叶子的路径
        ArrayList<String> arrayList = new ArrayList<>();
        // 对根节点为空这种特殊情况的处理
        if(root == null)
            return arrayList;
        // 储存遍历的路径
        ArrayList<Integer> arrayListSingle = new ArrayList<>();
        // 先把根节点存进去
        arrayListSingle.add(root.val);
        // 开始递归前序遍历二叉树
        go(root,arrayListSingle,arrayList);
        return arrayList;
    }
    public static void go(TreeNode node,ArrayList<Integer> arr, ArrayList<String> arrayStr) {
        // 遍历左节点
        if(node.left != null) {
            // 在遍历的路径中添加马上开始遍历的左节点，开始遍历左节点
            arr.add(node.left.val);
            go(node.left,arr,arrayStr);
            // 遍历完左节点，从遍历的路径中删除左节点
            arr.remove(arr.size() - 1);
        }
        // 遍历右节点
        if(node.right != null){
            // 在遍历的路径中添加马上开始遍历的右节点，开始遍历右节点
            arr.add(node.right.val);
            go(node.right,arr,arrayStr);
            arr.remove(arr.size() - 1);
        }
        // 当左右节点都空时，说明这个节点是叶子节点，把当前路径处理下格式，放到最终的结果list中
        if(node.left == null && node.right == null) {
            String temp = "" + arr.get(0);
            for (int i = 1; i < arr.size(); i++) {
                temp = temp + "->" + arr.get(i);
            }
            arrayStr.add(temp);
        }
    }
}