題目描述
給定一個(gè)二叉樹混坞，它的每個(gè)結(jié)點(diǎn)都存放一個(gè)0-9的數(shù)字第献，每條從根到葉子節(jié)點(diǎn)的路徑都代表一個(gè)數(shù)字破加。
例如俱恶，從根到葉子節(jié)點(diǎn)路徑 1->2->3代表數(shù)字 123。
計(jì)算從根到葉子節(jié)點(diǎn)生成的所有數(shù)字之和范舀。
說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)合是。
相關(guān)話題：?樹、深度優(yōu)先搜索????難度：?中等
示例1：
示例2：
思路：
- 首先是先序遍歷锭环，每遍歷到一個(gè)節(jié)點(diǎn)聪全，如果該節(jié)點(diǎn)不是null，用傳進(jìn)來的sum * 10 + 當(dāng)前節(jié)點(diǎn)的值
sum = sum * 10 + root.val;當(dāng)當(dāng)前節(jié)點(diǎn)是葉子節(jié)點(diǎn)辅辩，返回sum难礼，這就是一條路徑的值。這是遞歸的子問題 - 遞歸左玫锋、右子樹蛾茉，返回左右子樹的值的和。
return sumNumbers(root.left,sum) + sumNumbers(root.right,sum);
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int sumNumbers(TreeNode root) {
return sumNumbers(root, 0);
}
public int sumNumbers(TreeNode root, int sum){
if(root == null) return 0;
sum = sum * 10 + root.val;
if(root.left == null && root.right == null)
return sum;
return sumNumbers(root.left,sum) + sumNumbers(root.right,sum);
}
}
總結(jié)：遞歸算法將大問題看小的思路實(shí)在是在奇妙了撩鹿。
- 在做遞歸的題時(shí)谦炬，有時(shí)候我們需要另起一個(gè)函數(shù)，然后在另一個(gè)函數(shù)中調(diào)用三痰。例如本題另起了一個(gè)函數(shù)
sumNumbers(TreeNode root, int sum)吧寺。因?yàn)樵谒阋粭l路徑的值時(shí)，是一種自頂向下的遞歸散劫，必須接受上一步傳遞下來的結(jié)果稚机，是一步一步更新的過程，所以需要sum的輔助获搏。而在做斐波那契數(shù)列時(shí)赖条，那是一個(gè)自底向上的遞歸，例如要算f(n)常熙，就要知道f(n-1)纬乍，一直推到f(1)，在此之前并沒有結(jié)果算出來裸卫。 - 二叉樹的遞歸離不開左仿贬、右子樹，根據(jù)實(shí)際問題需要確定子問題墓贿， 每個(gè)遍歷到每個(gè)節(jié)點(diǎn)所需要做的操作(
sum = sum * 10 + root.val)茧泪，以及遞歸返回的條件(葉子節(jié)點(diǎn)時(shí)返回結(jié)果sum)蜓氨，然后就是借助左右思想return sumNumbers(root.left,sum) + sumNumbers(root.right,sum);。
做什么操作队伟，什么時(shí)候返回
