二叉树第四天！经过昨天的层序遍历专项梳理，目前我写层序遍历那是手到擒来、手拿把掐。
题目链接：513. 找树左下角的值
状态：看到题目直接用层序遍历秒杀了解题思路思路，但是因为不知道如何精准控制到每层都只记录第一个数字，所以后续看解析才写到AC。
看到题第一反应：wow！这不是昨天现学的层序遍历么，我只需在每层遍历的时候记录其第一个元素就好了。
然而，在做题的时候，我的内层循环使用的while，所以我怎么也想不到只控制第一个数字的方法。后来看到了教程才意识到原来把内层while循环换成for循环，然后在i=0的时候就是最左边的元素了 - - 也是成功拿下！
但是在此，我也试图掌握一下递归法。
大体思路是会有两个全局变量来分别记录 最深深度 和 结果，然后在每次递归的时候通过判断深度是否增加了来决定是否记录当前节点的结果。只要是深度变深，那就记录当前节点的结果，所以最终 结果 里装着的数据就是答案。在此值得注意的是 回溯里的操作（我写在了代码的注释里）。完整代码如下：
class Solution { // Java
private int result = Integer.MIN_VALUE; // result for Level-order traversal (iterative method)
private int maxDepth = Integer.MIN_VALUE;
private int result2 = Integer.MIN_VALUE; // result for Recursion
public int findBottomLeftValue(TreeNode root) {
// Level-order traversal (iterative method)
// findBottomLeftValue3(root);
// return result;
// now, it's Recursion method
findLeftValue2(root, 0);
return result2;
}
public void findLeftValue2(TreeNode root, int depth){ // recursion
if(root == null) return;
if(root.left == null && root.right == null){
if(depth > maxDepth) {
maxDepth = depth;
result2 = root.val;
}
}
if(root.left != null) findLeftValue2(root.left, depth+1);
if(root.right != null) findLeftValue2(root.right, depth+1);
/*
这两步实际上是简写，它省略了 回溯的过程
实际上应该是（只拿其中一个举例）
if(root.right != null){
depth++;
findLeftValue2(root.right, depth);
depth--; // 这一步就是回溯，意在退回递归的上一个节点
}
而之所以可以直接写成这种省略成一行代码的版本，是因为在递归的时候传入的是depth+1，
这个过程既满足了depth++，又能保证depth值不变，
换句话说就是当下一层递归结束，回溯回来的时候，depth依旧是当前的值，相当于做了--（减减）操作
所以一行代码里实际上是包含了回溯的操作的
*/
}
public void findBottomLeftValue3(TreeNode root){ // Level-order traversal (iterative method)
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int levelSize = queue.size();
for(int i = 0; i < levelSize; i++){
TreeNode tempNode = queue.poll();
if(i == 0){
result = tempNode.val;
}
if(tempNode.left != null) queue.offer(tempNode.left);
if(tempNode.right != null) queue.offer(tempNode.right);
}
}
}
}
复杂度分析：
- 递归法（findLeftValue2方法）
时间复杂度：O(n). 因为每个节点被访问一次
空间复杂度：O(h). 取决于树高 - 层序遍历迭代法（findBottomLeftValue3方法）
时间复杂度：O(n). 每个节点被访问一次
空间复杂度：O(w). w是树的宽度，树的宽度决定了队列里放节点的个数，而最坏情况下，满二叉树的叶子节点个数为n/2。所以最坏情况是O(n)级别。
题目链接：112. 路径总和
状态：看到题目直接用递归秒杀了解题思路思路，但是不知道做减法最后与0做比较会比较简单，所以后续看解析才写到AC。
看到题第一反应：这就是用递归遍历嘛，然后参数分别是root根节点，以及用于计算数字和的targetSum，返回值是boolean，因此此题是找到一个符合条件的就返回true，因此我们可以用boolea来判断是否找得到符合条件的结果，从而利用这个结果来实现 不用遍历完所有节点。终止条件就是遍历到叶子节点。然后单层递归逻辑就是把targetSum减去当前的节点的值然后传向下一层，同时如果上一层传回来的值如果是true的话，就继续把true往回传。完整代码如下：
class Solution { // Java
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null) return false;
targetSum -= root.val;
if(root.left == null && root.right == null) return targetSum == 0;
if(root.left != null){
boolean left = hasPathSum(root.left, targetSum);
if(left) return true; // find it
}
if(root.right != null){
boolean right = hasPathSum(root.right, targetSum);
if(right) return true; // find it
}
return false;
}
}
本题的递归体现在递归方法入口处的targetSum -= root.val; 这句话意味着接下来左右子节点传入到下一层递归的都是已经减过当前节点值的targetSum了。回溯体现在每次传往左右子树的targetSum都是独立的，换句话说就是传入右子树的targetSum不会受左子树代码的影响。所以用这种方式达到了回溯的目的。
复杂度分析：
时间复杂度：O(n). 最坏情况下所有节点都会被访问一次
空间复杂度：O(h). 取决于树高
题目链接：113. 路径总和 II
状态：不会，直接看的解析。
刚看题时的第一反应：好像就是在上一题的基础上增加一个记录路径的东西。但是因为这篇文章有点赶时间，所以选择直接看答案节约时间。
逻辑还是不变，只不过为了在递归过程中把结果传来传去所以递归方法的参数多加了两项。同时在回溯时，需要把路径去除掉最后一项（也就是最后加进来的 当前项）。完整代码如下：
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> result = new ArrayList<>();
if(root == null) return result;
List<Integer> path = new LinkedList<>();
preorderDFS(root, targetSum, result, path);
return result;
}
public void preorderDFS(TreeNode root, int targetSum, List<List<Integer>> result, List<Integer> path){
path.add(root.val);
if(root.left == null && root.right == null){
if(targetSum - root.val == 0){ // find it
result.add(new ArrayList<>(path));
}
return; // means the sum doesn't match
}
if(root.left != null){
preorderDFS(root.left, targetSum - root.val, result, path);
path.remove(path.size() - 1); // backtracking
}
if(root.right != null){
preorderDFS(root.right, targetSum - root.val, result, path);
path.remove(path.size() - 1); // backtracking
}
}
}
个人感觉是，如果造两个全局变量是不是就可以在参数上减少result和path两个参数了。
复杂度分析：
时间复杂度：O(n). 每个节点访问一次，访问的时候都是O(1)操作，所以整体还是O(n)
空间复杂度：O(n^2). 空间复杂度由两部分组成：递归栈的调用，O(h). 存储路径，O(hw).h是树高，w是树宽。因此最坏情况下，满二叉树的每条路径都是答案，那么就得存储h(n/2)的容量。所以是O(h*n)级别，而h最坏也可以达到n级别，所以综合来看，两部分加起来，是O(n^2)
