牛客面试高频榜单（第二组）难度：简单＆中等

（1）NC96 判断一个链表是否为回文结构

空间复杂度比较小的一种方式

1、找到对称点，将后面的链表反转 2、再继续进行比较

（2）NC5 二叉树根节点到叶子节点的所有路径和

有几个语法点

ArrayList 的 toString方法结果是将元素用逗号隔开的字符串

StringBuilder可通过deleteCharAt(index)删除对应位置的元素

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int sumNumbers (TreeNode root) {
        // write code here
        //注意为空树的情况
        if(root==null)
            return 0;
        //存储路径
        ArrayList<String> res = new ArrayList<String>();
        //维护路径
        StringBuilder arr = new StringBuilder();
        dfs(root,arr,res);
        int sum =0;
        for(String str:res){
            sum+=Integer.parseInt(str);
        }
        return sum;
    }
    //利用深度遍历
    private void dfs(TreeNode t, StringBuilder arr, ArrayList<String> res){
        arr.append(t.val);
        if(t.left!=null)
            dfs(t.left,arr,res);
        if(t.right!=null)
            dfs(t.right,arr,res);
        //当为叶子节点时，将路径加入
        if(t.left==null&&t.right==null){
            res.add(arr.toString());
        }
        //此节点遍历结束从维护路径中删除
        arr.deleteCharAt(arr.length()-1);
    }
}