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.从中序与后序遍历序列构造二叉树
题目链接：力扣
思路
分为6步：
1、后序数组为0，空节点
2、后序数组最后一个元素为节点元素
3、寻找中序数组位置作切割点
4、切中序数组
5、切后序数组
6、递归处理左区间、后区间
分解一下：
1、后序数组都是空了，就没有中了，就是空节点
2、后序数组中的最后一个元素是根节点的元素，根据根节点元素创建二叉树
3、切割点怎么找：遍历中序数组，找到根节点元素所在的下标位置
4、切割中序数组：为了得到左中序数组和右中序数组
5、切割后序数组：利用左中序数组进行切割，得到左后序数组和右后序数组
6、递归处理分割出来的数组
左节点 =递归函数（左中序数组，左后序数组）
右节点 =递归函数（右中序数组，右后序数组）
这道题目的整体思路是不难的，难的是代码的书写，比较容易转不去来，多写几遍，手动运行一下代码会更好理解
从中序与后序遍历序列构造二叉树
class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { if (inorder.length == 0 || postorder.length == 0) { return null; } // 左闭右开的原则 return traversal(inorder,0,inorder.length,postorder,0,postorder.length); } // 因为递归的时候，要传递两个数组的其实位置和结束位置，需要确定递归函数 public TreeNode traversal(int[] inorder, int inBegin, int inEnd,int[] postorder,int postBegin,int postEnd) { // 1、后序数组为0，空节点 if (postBegin == postEnd) { return null; } // 2、后序数组最后一个元素为节点元素 int nodeValue = postorder[postEnd - 1]; TreeNode root = new TreeNode(nodeValue); // 构造节点 // 3、寻找中序数组位置作切割点 // 遍历中序数组，找出和后序数组中最后一个元素相同的元素下标 int index; for (index = inBegin; index < inEnd; index++) { if (inorder[index] == nodeValue) { break; } } // 4、切割中序数组 // 左中序区间，左闭右开[inBegin,index) int leftInBegin = inBegin; int leftInEnd = index; // 这里是开，左区间是取不到的 // 右中序区间，左闭右开[index + 1,inEnd) int rightInBegin = index + 1; int rightInEnd = inEnd; // 5、切割后序数组 // 中序数组的左中序数组就是后序数组的左后序数组 // 左后序数组，左闭右开[postBegin,postBegin + (左中序区间的长度)) int leftPostBegin = postBegin; int leftPostEnd = postBegin + (index - inBegin); // 右后序数组，左闭右开[postBegin + (index - inBegin),postEnd - 1) int rightPostBegin = postBegin + (index - inBegin); int rightPostEnd = postEnd - 1; // 排除最后一个元素 这个元素已经成为节点了 // 6、递归处理左区间、后区间 root.left = traversal(inorder,leftInBegin,leftInEnd,postorder,leftPostBegin,leftPostEnd); root.right = traversal(inorder,rightInBegin,rightInEnd,postorder,rightPostBegin,rightPostEnd); return root; } }
105.从前序与中序遍历序列构造二叉树
题目链接：力扣
思路
与106的题目思路相同
从前序与中序遍历序列构造二叉树
class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder.length == 0 || inorder.length == 0) { return null; } return treaversal(preorder,0,preorder.length,inorder,0,inorder.length); } public TreeNode treaversal(int[] preorder,int preBegin,int preEnd,int[] inorder,int inBegin, int inEnd) { // 1、处理空数组 if (preBegin == preEnd) { return null; } // 2、取前序数组的第一个元素 int nodeValue = preorder[preBegin]; TreeNode node = new TreeNode(nodeValue); // 3、根据中节点分割中序数组 int index; for (index = inBegin;index<inEnd;index++) { if (inorder[index] == nodeValue) { break; } } // 4、切割中序数组 // 左中序数组 int leftInBegin = inBegin; int leftInEnd = index; // 右中序数组 int rightInBegin = index + 1; int rightInEnd = inEnd; // 5、切割前序数组 // 左前序数组 int leftPreBegin = preBegin + 1; int leftPreEnd = preBegin + 1 + (index - inBegin); // 右前序数组 int rightPreBein = preBegin + 1 + (index - inBegin); int rightPreEnd = preEnd; // 6、递归数组 node.left = treaversal(preorder,leftPreBegin,leftPreEnd,inorder,leftInBegin,leftInEnd); node.right = treaversal(preorder,rightPreBein,rightPreEnd,inorder,rightInBegin,rightInEnd); return node; } }
