南京市网站开发,wordpress国内打开速度慢,国外网页模板网站,seo优化需要多少钱题目
在一棵二叉树中所有节点都在0#xff5e;9的范围之内#xff0c;从根节点到叶节点的路径表示一个数字。求二叉树中所有路径表示的数字之和。例如#xff0c;图8.4的二叉树有3条从根节点到叶节点的路径#xff0c;它们分别表示数字395、391和302#xff0c;这3个数字…题目
在一棵二叉树中所有节点都在09的范围之内从根节点到叶节点的路径表示一个数字。求二叉树中所有路径表示的数字之和。例如图8.4的二叉树有3条从根节点到叶节点的路径它们分别表示数字395、391和302这3个数字之和是1088。
分析
首先考虑如何计算路径表示的数字。顺着指向子节点的指针路径向下遍历二叉树每到达一个节点相当于在路径表示的数字末尾添加一位数字。例如在最开始到达根节点时它表示数字3。然后到达节点9此时路径表示数字393×10939。然后向下到达节点5此时路径表示数字39539×105395。
这就是说每当遍历到一个节点时都计算从根节点到当前节点的路径表示的数字。如果这个节点还有子节点就把这个值传下去继续遍历它的子节点。先计算到当前节点为止的路径表示的数字再计算到它的子节点的路径表示的数字这实质上就是典型的二叉树前序遍历。
解
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);}
}
