**
Question:
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.
**
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int sumNumbers(TreeNode root) {
return getSum(root, "");
}
private int getSum(TreeNode root, String numStr) {
if (root == null)
return 0;
int subSum = 0;
if (root.left == null && root.right == null) {
subSum = Integer.parseInt(numStr + Integer.toString(root.val));
return subSum;
}
else if (root.left == null) { // left empty, right full
subSum = getSum(root.right, numStr + Integer.toString(root.val));
return subSum;
}
else if (root.right == null) { // left full, right empty
subSum = getSum(root.left, numStr + Integer.toString(root.val));
return subSum;
}
else {
subSum = getSum(root.left, numStr + Integer.toString(root.val));
subSum += getSum(root.right, numStr + Integer.toString(root.val));
return subSum;
}
}
}
My test result:
這次作業(yè)難度是Medium。。。但是我花了十幾分鐘就寫出來了。基本是一次通過。。
感覺很簡單。也就是樹的遍歷么。寫一個(gè)遞歸。然后判斷不同的情況。比DP要好想多了。
當(dāng)然，我剛剛說的基本一次通過。有個(gè)小錯(cuò)誤，就是一開始傳入的root可能就是null。其實(shí)這也沒多大意義。那就再加一個(gè)判斷就行了。
**
總結(jié)：
實(shí)在沒啥好總結(jié)的。。。
DFS。深度遍歷。我的確用到了。很享受DFS。然后BFS好像很少用。因?yàn)锽FS的結(jié)構(gòu)不適合遞歸。需要用一個(gè)隊(duì)列來實(shí)現(xiàn)BFS。而DFS需要用一個(gè)棧來實(shí)現(xiàn)。遞歸正好自帶棧結(jié)構(gòu)。所以就對(duì)上啦！
然后
int -> String: String str = Integer.toString(i);
String -> int: int i = Integer.parseInt(str);
**
今天看了C++template.
這一塊是很復(fù)雜的東西。憑我現(xiàn)在的理解是無法徹底弄清楚的，更別說總結(jié)了。
template是靜態(tài)的，所以在編譯的時(shí)候就完成了。是static polymorphism.
inheritance是動(dòng)態(tài)的，所以在運(yùn)行狀態(tài)完成。是 dynamic polymorphism.
Java中的多態(tài)，說到底，都是繼承，沒有模板這種靜態(tài)的多態(tài)存在。
但C++既有模板，又有繼承。既有命令式編程（C/Java），又有函數(shù)式編程（lambda expression）.
C語言也是有多態(tài)特性的，這種多態(tài)和Java類似，是動(dòng)態(tài)的多態(tài)。
通過 void * 作為父類（相當(dāng)于Java中的Object類）實(shí)現(xiàn)向上繼承和向下繼承，以此來實(shí)現(xiàn)，C語言的多態(tài)。
突然發(fā)現(xiàn)康村的CS教學(xué)視頻我全部可以在網(wǎng)上看，通過他的平臺(tái)。。。得抓緊時(shí)間學(xué)習(xí)了。
當(dāng)然，當(dāng)務(wù)之急，是搞好接下來的七門考試！還有簽證！還有畢業(yè)！還有日本！
Anyway, Good luck, Richardo!
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private int sum = 0;
public int sumNumbers(TreeNode root) {
if (root == null)
return 0;
dfs(root, 0);
return sum;
}
private void dfs(TreeNode root, int pre) {
if (root == null)
return;
else if (root.left == null && root.right == null) {
sum += 10 * pre + root.val;
return;
}
int curr = 10 * pre + root.val;
dfs(root.left, curr);
dfs(root.right, curr);
}
}
這次寫的比第一次簡潔多了。
一個(gè) pre-order 解決問題。
樹的解決問題方式必須依靠訪問，訪問無非四種方式。
Anyway, Good luck, Richardo!
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int sumNumbers(TreeNode root) {
if (root == null) {
return 0;
}
return helper(root, 0);
}
private int helper(TreeNode root, int prev) {
int curr = root.val + 10 * prev;
if (root.left == null && root.right == null) {
return curr;
}
else if (root.left == null) {
return helper(root.right, curr);
}
else if (root.right == null) {
return helper(root.left, curr);
}
else {
return helper(root.left, curr) + helper(root.right, curr);
}
}
}
不難。
Anyway, Good luck, Richardo! -- 08/28/2016
