java算法day16

java算法day16

• 112 路径总和
• 404 左叶子之和
• 513 找树左下角的值

---

112 路径总和

题型判定为自顶向下类型，并且为路径和类型。
那就套模板。
自顶向下就是从上到下处理，那么就是前序遍历的思想。

class Solution {boolean res = false;public boolean hasPathSum(TreeNode root, int targetSum) {//特判if(root==null&&targetSum==0){return false;}//递归dfs(root,targetSum);return res;}//递归void dfs(TreeNode root,int targetSum){if(root==null){return;}//过程就是不断往下递归，成功的条件是叶子节点，targetSum-=root.val;if(root.left==null && root.right==null & targetSum==0){res = true;}else{//递归左右子树dfs(root.left,targetSum);dfs(root.right,targetSum);}}
}

本题得到的知识。
因为我是按模板做的，这个题我非常想在遇到结果的时候就立即返回。但是用模板做，那肯定会把全局走完。因此新知识就是怎么实现立即返回。

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if(root==null&&targetSum==0){return false;}return dfs(root,targetSum);}boolean dfs(TreeNode root,int targetSum){if(root==null){return false;}targetSum-=root.val;if(root.left==null && root.right==null & targetSum==0){//完全可以直接返回return true;}//核心思想在理解这里return dfs(root.left,targetSum) || dfs(root.right,targetSum);}
}

通过这个题，我对递归的理解又更近了一步，更新我的想法。
return dfs(root.left,targetSum) || dfs(root.right,targetSum);
这里的正确想法是，递归左右子树，实际上是递归到最左底层后，往上回溯一层，然后才是去递归右子树。所以根据短路操作，碰到返回true，那么反馈给上层，上层得到这个true，就会把还没递归的右子树给短路。实现了建制。要是按我之前的做法，回溯的过程，每个右子树都是会去递归的。在某些大型树的场景就效率低了。

---

404 左叶子之和

这题就两个难点，左叶子点怎么定义。如果你对什么是左叶子点很清楚，那这个题就很容易。

ps：千万别层序遍历去做，层序遍历根本判别不了叶子节点是左叶子节点还是右叶子节点

1、左叶子点：某点的左孩子节点，其左孩子节点的左右孩子都为null，那么这个节点就是左叶子点。

2、在递归的时候很容易空指针，如何解决？
用短路操作把容易空指针的提前断掉。

先序遍历的思想

class Solution {int sum = 0;public int sumOfLeftLeaves(TreeNode root) {dfs(root);return sum;}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);}
}

---

513 找树左下角的值

树左下角的值，题目给的定义就是，最后一层，最左的节点。

所以我当时就立马想到了层序遍历的做法，我在迭代每一层的元素的时候，每次把每一层的第一个元素的值存下来还是很容易的。因此马上做了出来。

class Solution {public int findBottomLeftValue(TreeNode root) {Deque<TreeNode> que = new ArrayDeque<>();que.offerLast(root);int res = 0;while(!que.isEmpty()){int size = que.size();//每次扩展的时候，只存第一个扩展节点的值，全部处理完，结果就是这个for(int i = 0;i<size;i++){TreeNode temp = que.pollFirst();//关键就在这，每层处理一下第一个节点。if(i==0){res = temp.val;}if(temp.left!=null){que.offerLast(temp.left);}if(temp.right!=null){que.offerLast(temp.right);}}}return res;}
}

我提交之后发现，效率可以说非常的低。

递归解法：
要点：
1、实际上转化成了找深度最深的节点。
2、由于要保证最左，那递归的时候肯定优先递归左边，所以可以用先序遍历。

过程中的难点：
1、我在过程中老是在想一找到就立刻返回。实际上这是不太现实的。因为路没走完，你根本不可能知道哪个节点才是最深的。因此这个过程应该是不断的寻找最深节点，一旦找到更深的节点，那就应该把该点的值存下来。
2、起点深度怎么定其实无所谓的，最重要的是往下迭代深度的过程。所以一开始设置maxDepth=-1就行了，result=0。那么起点就一定要把maxDepth覆盖。

class Solution {int maxDepth = -1;int result = 0;public int findBottomLeftValue(TreeNode root) {dfs(root,0);return result;}void dfs(TreeNode node,int depth){if(node==null){return ;}//我一开始从0相当于先走一步了，所以都是往下递归才+1.if(depth>maxDepth){maxDepth = depth;result = node.val;}dfs(node.left,depth+1);dfs(node.right,depth+1);}
}

---