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

分析

• 每条从根到叶子节点的路径都代表一个数字
• 寻找的是符合条件的所有路径之和

解法一：深度优先遍历（DFS）

思路步骤：

• 每一个结点对应的数字=其父节点对应数字*10加上该结点的值
• 假设根节点的父亲节点对应的数字为0
• 计算出每一个叶子节点对应的数字
• 计算所有叶子节点对应的数字之和

图解

Java参考代码：

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int sumNumbers (TreeNode root) {
        // 调用dfs
        return dfs(root,0);
    }
    //深度优先搜索
    public int dfs(TreeNode root,int sum){
        if(root==null){
            return 0;
        }
        int total = sum*10+root.val;
        //已达到叶子节点，返回结果
        if(root.left==null && root.right==null){
            return total;
        }else{
            //递归调用
             return dfs(root.left,total)+dfs(root.right,total);
        }

    }
}

复杂度分析

时间复杂度：O(N) 其中 N 是二叉树的节点个数。对每个节点访问一次。

空间复杂度：O(N) 其中 N 是二叉树的节点个数。复杂度主要取决于递归调用的栈空间，最坏情况下，二叉树的高度等于节点个数。

解法二：广度优先遍历（BFS）

思路步骤：

• 创建两个队列分别存放节点和节点对应的数字
• 不断维护以上两个队列
• 将根节点与其值分别入队
• 每次从俩队列分别出队取到一个节点和一个数值
• 如果取出的节点是不是叶子节点，获取该结点的非空子节点，并根据该结点对应的数字和子节点的值计算子节点对应的数字，
• 将子节点和子节点对应的数字分别入队
• 如果当前取出的结点是叶子节点，则累加该结点对应的数字。
• 广搜结束，即可得到所有叶子结点对应的数字之和
• 返回答案

图解