**
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:
这次作业难度是Medium。。。但是我花了十几分钟就写出来了。基本是一次通过。。
感觉很简单。也就是树的遍历么。写一个递归。然后判断不同的情况。比DP要好想多了。
当然，我刚刚说的基本一次通过。有个小错误，就是一开始传入的root可能就是null。其实这也没多大意义。那就再加一个判断就行了。
**
总结：
实在没啥好总结的。。。
DFS。深度遍历。我的确用到了。很享受DFS。然后BFS好像很少用。因为BFS的结构不适合递归。需要用一个队列来实现BFS。而DFS需要用一个栈来实现。递归正好自带栈结构。所以就对上啦！
然后
int -> String: String str = Integer.toString(i);
String -> int: int i = Integer.parseInt(str);
**
今天看了C++template.
这一块是很复杂的东西。凭我现在的理解是无法彻底弄清楚的，更别说总结了。
template是静态的，所以在编译的时候就完成了。是static polymorphism.
inheritance是动态的，所以在运行状态完成。是 dynamic polymorphism.
Java中的多态，说到底，都是继承，没有模板这种静态的多态存在。
但C++既有模板，又有继承。既有命令式编程（C/Java），又有函数式编程（lambda expression）.
C语言也是有多态特性的，这种多态和Java类似，是动态的多态。
通过 void * 作为父类（相当于Java中的Object类）实现向上继承和向下继承，以此来实现，C语言的多态。
突然发现康村的CS教学视频我全部可以在网上看，通过他的平台。。。得抓紧时间学习了。
当然，当务之急，是搞好接下来的七门考试！还有签证！还有毕业！还有日本！
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);
}
}
这次写的比第一次简洁多了。
一个 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
