Path for Binary Tree

Print all the paths from root to every leaf in a binary tree


Naive Thinking: 可以用stack进行DFS，同时还要回溯，也可以用recursive的DFS，避免些回溯的麻烦。

算法复杂度是O(n), space是O(n)。

import java.util.List;
import java.util.ArrayList;

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val = x;
        left = null;
        right = null;
    }
}

public class Solution{

    public static void main(String args[]){
        Solution s = new Solution();
        int n = 10;
        TreeNode[] tree = new TreeNode[n];
        for(int i = 0;i < n;i++)
            tree[i] = new TreeNode(i);
        for(int i = 0;2*i+2 < n;i++){
            tree[i].left = tree[2*i+1];
            tree[i].right = tree[2*i+2];
        }
        List<List<Integer>> list = s.pathsForBinaryTree(tree[0]);
        for(int i = 0;i < list.size();i++)
            System.out.println(list.get(i));

    }

    public List<List<Integer>> pathsForBinaryTree(TreeNode root){
        // recursive DFS
        List<List<Integer>> rlst = new ArrayList<List<Integer>>();
        if(root==null){return rlst;}
        search(new ArrayList<Integer>(), rlst, root);
        return rlst;
    }

    private void search(List<Integer> list, List<List<Integer>> rlst, TreeNode root){
        List<Integer> newList = new ArrayList<Integer>(list);
        newList.add(root.val);
        if(root.left==null && root.right==null)
            rlst.add(newList);
        else{
            if(root.left!=null)
                search(newList, rlst, root.left);
            if(root.right!=null)
                search(newList, rlst, root.right);
        }
    }

}