本文共 2616 字，大约阅读时间需要 8 分钟。

DESC:

题目描述

给定一个仅包含数字 0−9 的二叉树，每一条从根节点到叶子节点的路径都可以用一个数字表示。

例如根节点到叶子节点的一条路径是1→2→3,那么这条路径就用123 来代替。

找出根节点到叶子节点的所有路径表示的数字之和

例如：

这颗二叉树一共有两条路径，

根节点到叶子节点的路径 1→2用数字 12 代替

根节点到叶子节点的路径 1→3 用数字 13 代替

所以答案为 12+13=25

示例1

输入

{1,0}

返回值

10

示例2

输入

{1,#,9}

返回值

19

CODE1:

JAVA:

import java.util.*;/* * public class TreeNode { *   int val = 0; *   TreeNode left = null; *   TreeNode right = null; * } */public class Solution {    /**     *      * @param root TreeNode类      * @return int整型     */    private List
    
      pathList = new ArrayList<>();    public int sumNumbers (TreeNode root) {        // write code here        dfs(root, new StringBuilder());        int res = 0;        for (String path: pathList) {            res += Integer.parseInt(parsePath(path));        }        return res;    }        private void dfs(TreeNode node, StringBuilder path) {        if (node == null) {            return;        }        path.append(node.val);        if (node.left == null && node.right == null) {            pathList.add(path.toString());        } else {            dfs(node.left, path);            dfs(node.right, path);        }        path = path.deleteCharAt(path.length()-1);    }        private String parsePath (String path) {        StringBuilder sb = new StringBuilder();        boolean flag = true;        for (char c : path.toCharArray()) {            if (c == '0' && flag) {                continue;            } else {                sb.append(c);                flag = false;            }        }        if (sb.length() == 0) {            return "0";        }        return sb.toString();    }}
    

 

 NOTES1:

1. dfs，回溯
2. 惯性思路：字符串拼接所有的根节点到叶子节点的路径，最后解析成数字并求和，还要注意用完回溯

CODE2:

JAVA:

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {    public int sumNumbers(TreeNode root) {        return this.dfs(root, 0);    }    public int dfs(TreeNode node, int preSum) {        if (node == null) {            return 0;        }        preSum = preSum * 10 + node.val;        if (node.left == null && node.right == null) {            return preSum;        } else {            return this.dfs(node.left, preSum) + this.dfs(node.right, preSum);        }    }}

 

NOTES2:

1. dfs
2. 递归深度搜索的过程中直接计算到当前节点的前缀路径和，sum=sum*10+val; 如果到达了根节点，当前sum就是一个有效路径sum，返回，如果不是根节点，就计算左右叶子节点有效路径和，最后到根节点，就是所有的有效路径sum，类似归并；这里要注意理解非叶子节点返回的是经过该节点的所有有效路径和；可以自底向上思考

转载地址：http://jfldi.baihongyu.com/