513.找树左下角的值
题目链接：力扣
思路
层序遍历的思路还是很好得到的，在每层的遍历中我们都可以得到最左边的数字，那么也是可以得到最底层的最左边的数字的，比递归法简单多了
使用递归的话也是可以找到最底层最左侧的值——最后一行找到最左侧的值，我们只要找到这棵树得最大深度，然后记录这层从左侧第一个值就可以了
那么前序(中左右)、后序(左右中)、中序(左中右)，都是可以的，因为不论是那种顺序的遍历，每一层都是会先处理左边再处理右边，这道题目没有中间节点处理的逻辑
所以通过递归要做两件事：
1、找到树的最大深度
2、记录最大深度的最左侧的值
找树左下角的值
递归法
定义一个变量，表示最大深度，记录所有深度中的最大深度
定义一个变量，表示结果，每层记录结果，最后结果中保存的是深度最大的一层的结果
递归函数：
处理根节点的参数，还有一个参数depth，记录当前深度
终止条件：
当遇到叶子节点的时候，就需要统计一下最大的深度了，并且更新值
通俗的想，直到找到最底层、最左侧的节点，我们就可以进行终止了
在遍历的时候，不论是哪种序的遍历方法，对当前层来说，总是左节点先进来判断的
而这里利用这个特性，深度加深，此层的第一个节点进来，判断，记录当前最大深度，然后记录节点的值，此时深度更新完毕，最左侧节点更新完毕
class Solution {
public int findBottomLeftValue(TreeNode root) {
// 根节点和其对应的深度
traversal(root,1);
return result;
}
int maxDepth = Integer.MIN_VALUE; //用来存放最大深度的
int result = 0; // 当深度增加时，保存这一层的第一个值
// 首先确定递归函数
void traversal(TreeNode node, int depth) {
if (node == null) {
return;
}
if (node.left == null && node.right == null) {
// 说明node是一个叶子节点
if (depth > maxDepth) {
maxDepth = depth;
result = node.val;
}
}
// 左
if (node.left != null) {
// 那就得探探你的深度了，找到你这边深度最大的叶子节点了
// 注意哈：traversal()的两个参数代表的意思是；这个节点,这个节点的深度
depth++;
traversal(node.left,depth);
depth--;
}
// 右
if (node.right != null) {
depth++;
traversal(node.right,depth);
depth--;
}
// 中
// 中不做处理
}
}迭代法
层序遍历，简单易懂好操作
class Solution {
public int findBottomLeftValue(TreeNode root) {
// 设这个要查找的值为0,使用层序遍历
// 每次遍历一层就将这个值重新赋值一下
int result = 0;
Deque<TreeNode> deque = new ArrayDeque<>();
deque.offer(root);
while (!deque.isEmpty()) {
int len = deque.size();
TreeNode leftnode = deque.peek();
result = leftnode.val;
for (int i = 0; i < len; i++) {
TreeNode node = deque.poll();
if (node.left != null) {
deque.offer(node.left);
}
if (node.right != null) {
deque.offer(node.right);
}
}
}
return result;
}
}112.路径总和
题目链接：力扣
思路
求出所有根节点到叶子节点的值的总和，然后看看其中有没有和目标值相等的值
那就需要收割所有路径的值，这跟 257.二叉树的所有路径 比较像，只不过多了一步处理
路径总和
递归法(全部遍历)
太激动了，第一次自己完整地写出来一道递归的题目
根据257的写法：
这种方法对于求所有的路径是很合适的，因为你一定要把所有的路径都添加进去。
但是这个题目没必要把左右的路径全部算出来，只要有符合路径的结果就可以了
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
List<TreeNode> nodes = new ArrayList<>();
List<Integer> allValue = new ArrayList<>();
if (root == null) {
return false;
}
nodesSum(root,nodes,allValue);
return allValue.contains(targetSum);
}
void nodesSum(TreeNode node, List<TreeNode> nodes, List<Integer> allValue) {
// 中
nodes.add(node);
// 终止条件
if (node.left == null && node.right == null) {
// 说明碰到这条路径的最后叶子节点了，收集这条路径上的结果
int sum = 0;
for (TreeNode value : nodes) {
sum += value.val;
}
allValue.add(sum);
}
// 左
if (node.left != null) {
nodesSum(node.left,nodes,allValue);
nodes.remove(nodes.size() - 1);
}
// 右
if (node.right != null) {
nodesSum(node.right,nodes,allValue);
nodes.remove(nodes.size() - 1);
}
}
}递归法(不用全部遍历)
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
return traversal(root,targetSum - root.val);
}
boolean traversal(TreeNode cur,int count) {
// 终止条件
// 遇到了叶子节点，并且目标值被减到0
if (cur.left == null && cur.right == null && count == 0) {
return true;
}
// 遇到了叶子节点，但是目标值没有被减到0
if (cur.left == null && cur.right == null) {
return false;
}
// 左
if (cur.left != null) {
count -= cur.left.val;
if (traversal(cur.left,count)) {
return true;
}
count += cur.left.val;
}
// 右
if (cur.right != null) {
count -= cur.right.val;
if (traversal(cur.right,count)) {
return true;
}
count += cur.right.val;
}
return false;
}
}113.路径总和||
题目链接：力扣
思路
跟257、二叉树的所有路径 力扣 112 路径总和 力扣 的原理是一样的，只是对结果的处理上有所不同
路径总和||
需要注意的点是：
在将List<Integer>添加到List<List<Integer>>中时，一定要新创建一个集合来保存结果，否则这个集合会被后面的程序改变，因为集合中保存的是内存地址
<--------错误实例： 
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> nodeVals = new ArrayList<>();
if (root == null) {
return result;
}
nodesList(root,nodeVals,result,targetSum);
return result;
}
void nodesList(TreeNode node,List<Integer> nodeVals,List<List<Integer>> result,int targetSum){
// 中
nodeVals.add(node.val);
// 终止条件
if (node.left == null && node.right == null) {
int sum = 0;
for (Integer nodeVal : nodeVals) {
sum += nodeVal;
}
if (sum == targetSum) {
// 要重新创建一个集合对象来保存这里的值，集合中只能保存地址
result.add(new ArrayList<>(nodeVals));
}
}
// 左
if (node.left != null) {
nodesList(node.left,nodeVals,result,targetSum);
nodeVals.remove(nodeVals.size() - 1);
}
// 右
if (node.right != null) {
nodesList(node.right,nodeVals,result,targetSum);
nodeVals.remove(nodeVals.size() - 1);
}
}
}106.从中序与后序遍历序列构造二叉树
题目链接
思路
从中序与后序遍历序列构造二叉树
105.从前序与中序遍历序列构造二叉树
题目链接