说是多叉树，其实都是其他的问题联想到多叉树，然后用树的方法来解决。

797. 所有可能的路径

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        res=new ArrayList<>();
        traverse(graph, 0, new ArrayList<>());
        return res;
    }
    public void traverse(int[][] graph,int index,List<Integer> list){
        list.add(index);
        if(index==graph.length-1){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i:graph[index]){
            traverse(graph,i,list);
            list.remove(list.size()-1);
        }
    }
}

上面traverse函数里面list.add(index)这一步的位置，一开始是这么写的，是错误的：
会输出：[[0,1,3][0,0,2,3]]
起点被加入了两次，那是因为逻辑错了，放到了遍历i里面，i有多少个，最后最多就会加多少次index

    public void traverse(int[][] graph,int index,List<Integer> list){
        if(index==graph.length-1){
            list.add(index);
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i:graph[index]){
            list.add(index);
            traverse(graph,i,list);
            list.remove(list.size()-1);
        }
    }

341. 扁平化嵌套列表迭代器

题解

public class NestedIterator implements Iterator<Integer> {
    private List<Integer> vals=new ArrayList<>();
    private int cur=0;

    public NestedIterator(List<NestedInteger> nestedList) {
        dfs(nestedList);
    }

    private void dfs(List<NestedInteger> nestedList){
        for(NestedInteger nestedInteger:nestedList){
            if(nestedInteger.isInteger()){
                vals.add(nestedInteger.getInteger());
            }else{
                dfs(nestedInteger.getList());
            }
        }
    }

    @Override
    public Integer next() {
        return vals.get(cur++);
    }

    @Override
    public boolean hasNext() {
        return cur<vals.size();
    }
}

208. 实现 Trie (前缀树)

class Trie {
    class TrieNode{
        boolean isEnd;
        TrieNode[] next;

        TrieNode(){
            isEnd=false;//表示该节点是否是某一个单词的结尾
            next=new TrieNode[26];//26个小写英文字母，表示下一位
        }
    }

    TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root=new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        char[] array=word.toCharArray();
        int len=array.length;
        TrieNode cur=root;
        for(int i=0;i<len;i++){
            int j=array[i]-'a';
            if(cur.next[j]==null){
                cur.next[j]=new TrieNode();
            }
            cur=cur.next[j];                
        }
        cur.isEnd=true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        char[] array=word.toCharArray();
        int len=array.length;
        TrieNode cur=root;
        for(int i=0;i<len;i++){
            int j=array[i]-'a';
            if(cur.next[j]==null) return false;
            cur=cur.next[j];
        }
        return cur.isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        char[] array=prefix.toCharArray();
        int len=array.length;
        TrieNode cur=root;
        for(int i=0;i<len;i++){
            int j=array[i]-'a';
            if(cur.next[j]==null) return false;
            cur=cur.next[j];
        }
        return true;
    }
}