题目
在一棵二叉树中所有节点都在0~9的范围之内,从根节点到叶节点的路径表示一个数字。求二叉树中所有路径表示的数字之和。例如,图8.4的二叉树有3条从根节点到叶节点的路径,它们分别表示数字395、391和302,这3个数字之和是1088。
分析
首先考虑如何计算路径表示的数字。顺着指向子节点的指针路径向下遍历二叉树,每到达一个节点,相当于在路径表示的数字末尾添加一位数字。例如,在最开始到达根节点时,它表示数字3。然后到达节点9,此时路径表示数字39(3×10+9=39)。然后向下到达节点5,此时路径表示数字395(39×10+5=395)。文章来源:https://www.toymoban.com/news/detail-740790.html
这就是说,每当遍历到一个节点时都计算从根节点到当前节点的路径表示的数字。如果这个节点还有子节点,就把这个值传下去继续遍历它的子节点。先计算到当前节点为止的路径表示的数字,再计算到它的子节点的路径表示的数字,这实质上就是典型的二叉树前序遍历。文章来源地址https://www.toymoban.com/news/detail-740790.html
解
public class Test {
public static void main(String[] args) {
TreeNode node3 = new TreeNode(3);
TreeNode node9 = new TreeNode(9);
TreeNode node0 = new TreeNode(0);
TreeNode node5 = new TreeNode(5);
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
node3.left = node9;
node3.right = node0;
node9.left = node5;
node9.right = node1;
node0.right = node2;
int result = sumNumbers(node3);
System.out.println(result);
}
public static int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
private static int dfs(TreeNode root, int sum) {
if (root == null) {
return 0;
}
sum = sum * 10 + root.val;
if (root.left == null && root.right == null) {
return sum;
}
return dfs(root.left, sum) + dfs(root.right, sum);
}
}
到了这里,关于面试算法49:从根节点到叶节点的路径数字之和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!