目录
- 1 题目描述:左叶子之和
- 2 实例:
- 3 思路:
- 4 遇上的问题:
- 5 结果
- 6 反思:
- 7 学习他人优秀的算法
- 8 学习他人的收获:
1 题目描述:左叶子之和
计算给定二叉树的所有左叶子之和
2 实例:
3 思路:
- 对拿到手的节点进行判断,如果左节点不为空,左节点递归,如果右节点不为空,右节点递归,如果节点下左右节点都为空,则返回节点值。
4 遇上的问题:
- 首先确定要返回叶子节点。叶子节点特征,左右节点都为空。
- 接着是要舍去右叶子节点返回值,在右节点进行递归的时候,调用另一个方法为了避免传进去的右节点是右叶子节点。
- 传递进来的树只有1个数或者0个数的情况,对第一次传递的树进行1个或0个判断,如果判断成功,直接返回0。
5 结果
6 反思:
- 对树节点递归不熟练,不知道可以节点.节点.节点的操作,只是以为只可以节点.节点。今天收获get+1!如果不知道节点.节点.节点的操作,就不能判断传进去的节点是否为左叶子节点,当时写解法的时候还很疑惑。
- 在解题过程中,拿到主要思路就开始写,然后遇到算法没考虑的问题就开始改算法。算法考虑不足。需要更多的训练。
- 写出来的算法冗杂不简洁可读性差,看起来很丑。
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
int sum = 0;
if(root == null)
return 0;
if(root.left==null&&root.right==null){
return 0;
}
if(root.left!=null){
sum = sum + noTop(root.left);
}
if(root.right!=null){
sum= sum + right(root.right);
}
if(root.left==null&&root.right==null){
sum = sum+root.val;
}
return sum;
}
public int noTop(TreeNode root){
int sum = 0;
if(root.left!=null){
sum = sum + noTop(root.left);
}
if(root.right!=null){
sum= sum + right(root.right);
}
if(root.left==null&&root.right==null){
sum = sum+root.val;
}
return sum;
}
public int right(TreeNode root){
int sum = 0;
if(root.left==null&&root.right==null){
return 0;
}
if(root.left!=null){
sum = 0 + noTop(root.left);
}
if(root.right!=null){
sum= sum + right(root.right);
}
return sum;
}
}
7 学习他人优秀的算法
执行消耗内存为 37060 kb 的范例,内存消耗最前列。
class Solution {
int sum=0;
public int sumOfLeftLeaves(TreeNode root) {
if(root==null) return sum;
dfs(root);
return sum;
}
private void dfs(TreeNode root){
if(root==null) return;
if(root.left!=null&&root.left.left==null&&root.left.right==null){
sum+=root.left.val;
}
dfs(root.left);
dfs(root.right);
}
}
时间最前列,
第二个算法在判断是否左叶子节点的算法上加了一个boolean值来判断传进来的节点是否为左叶子节点。这个想法有冒出来过,可惜我是在原方法进行修改,然后报错,还以为不能这样做,我还是太嫩了!
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
return sumofleavesHelper(root, false);
}
public int sumofleavesHelper(TreeNode root, boolean leftOrRight){
if(root == null) return 0;
int counter = 0;
int left = sumofleavesHelper(root.left,true);
int right = sumofleavesHelper(root.right, false);
if(leftOrRight && root.left == null && root.right == null){
counter = root.val;
}
return left + right + counter;
}
}
8 学习他人的收获:
- 定义了一个全局变量sum,
- 原方法是规定死的,但是原方法可以调用可以有自己的想法的自定义方法。
鸢飞莺舞,只愿执心继续前行 ----Swrici
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)