分析
- 每条从根到叶子节点的路径都代表一个数字
- 寻找的是符合条件的所有路径之和
解法一:深度优先遍历(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)
思路步骤:
- 创建两个队列分别存放节点和节点对应的数字
- 不断维护以上两个队列
- 将根节点与其值分别入队
- 每次从俩队列分别出队取到一个节点和一个数值
- 如果取出的节点是不是叶子节点,获取该结点的非空子节点,并根据该结点对应的数字和子节点的值计算子节点对应的数字,
- 将子节点和子节点对应的数字分别入队
- 如果当前取出的结点是叶子节点,则累加该结点对应的数字。
- 广搜结束,即可得到所有叶子结点对应的数字之和
- 返回答案