题解 | #二叉树根节点到叶子节点的所有路径和#

方法一（深度优先搜索）

1.题意整理

• 给定一颗二叉树，二叉树中每个节点对应一个节点值（在0-9范围内）。
• 求二叉树中所有路径的和，每一条路径指的是从根节点到某一个叶子节点这一串节点值从高位到低位组成的数。

2.思路整理

题目需要求所有路径和，所以只要找出每一条路径，然后记录对应路径的变化，最后将所有路径相加即可。可以采用深度优先搜索找路径，每次遇到叶子节点，则表示当前路径搜索完毕。

• 递归终止条件：当搜索完所有路径，递归终止，即root为空。
• 递归如何传递：每一次都会尝试往当前节点的左子节点和右子节点走，由于每次路径开始时，path都要重置为0，所以每次选择左子节点或右子节点之后，都会回溯到选择之前的状态，即$path\mathrm{/}=10path/=10$。比如下图中的例子，当前节点是1，选择2、5之后，path变为125，接着要遍历另一条路径10，如果不回溯，path就会变为1250，显然不合法，而回溯之后，path重新变为1，加上右子节点0，路径为10。

图解展示：

3.代码实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    //记录所有路径和
    int res=0;
    //记录某一条路径
    int path=0;
    public int sumNumbers (TreeNode root) {
        //深度优先搜索
        dfs(root);
        return res;
    }
    
    //深度优先搜索
    private void dfs(TreeNode root){
        //为空直接返回
        if(root==null) return;
        //记录当前路径的变化
        path=path*10+root.val;
        //遇到叶子节点，说明路径结束，加入到res
        if(root.left==null&&root.right==null){
            res+=path;
        }
        //往左子树和右子树遍历
        dfs(root.left);
        dfs(root.right);
        //回溯到上一个节点的位置
        path/=10;
    }
}

4.复杂度分析

• 时间复杂度：需要遍历二叉树中所有节点，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：递归栈的深度为$lo{g}_{2}nlog\_2n$，当退化为链表时，深度为n，所以空间复杂度为$O(n)O(n)$。