给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字:
例如,从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
分析:本题相加的每个数字都是从根节点出发得到的,必须要遍历二叉树的每个节点,那么自然会有回溯的思想,首先定义全局变量ret作为最后的返回值,然后定义num作为递归中的数字,当判断当前节点是叶子结点时,使用回溯思想,先将结果存入,然后将num回溯
参考代码:
class Solution {public int sumNumbers(TreeNode root) {sup(root,0);return sum;}int sum=0;private void sup(TreeNode node,int num){if(node.left==null&&node.right==null){num=num*10+node.val;sum+=num;num/=10;return;}num=num*10+node.val;if(node.left!=null) sup(node.left,num);if(node.right!=null) sup(node.right,num);}}
