分析

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

解法一:深度优先遍历(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)

思路步骤:

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

图解