今日任务
力扣 513. 找树左下角的值, 112. 路径总和, 113. 路径总和 II, 106. 从中序与后序遍历序列构造二叉树
题目 ：513. 找树左下角的值
思路
递归，最大深度的 最左值就是答案
题解
class Solution {
int Deep = -1;
int value = 0;
public int findBottomLeftValue(TreeNode root) {
value = root.val;
findLeftValue(root, 0);
return value;
}
public void findLeftValue(TreeNode root, int deep) {
if (root == null)
return;
if (root.left == null && root.right == null) {
if (deep > Deep) {
Deep = deep;
value = root.val;
}
}
if (root.left != null)
findLeftValue(root.left, deep + 1);
if (root.right != null)
findLeftValue(root.right, deep + 1);
}
}题目 ：112. 路径总和
思路
先明确是递归
递归三部曲：
①确定递归函数的参数和返回类型
图中可以看出，遍历的路线，并不要遍历整棵树，所以递归函数需要返回值，可以用bool类型表示。
②确定终止条件
首先计数器如何统计这一条路径的和呢？
用递减代替累加，如果最后count == 0，同时到了叶子节点的话，说明找到了目标和。
如果遍历到了叶子节点，count不为0，就是没找到。
③确定单层递归的逻辑
因为终止条件是判断叶子节点，所以递归的过程中就不要让空节点进入递归了。
递归函数是有返回值的，如果递归函数返回true，说明找到了合适的路径，应该立刻返回。
题解
class Solution {
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;
}
if (root.right != null) {
boolean right = hasPathSum(root.right, targetSum);
if (right) return true;
}
return false;
}
}题目 ： 113. 路径总和 II
思路
与112不同的是这道题需要记录路径。因此要复杂些许，需要额外开数组、dfs回溯
题解
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
List<Integer> path = new LinkedList<>();
dfs(root, targetSum, res, path);
return res;
}
public void dfs(TreeNode root, int targetSum, List<List<Integer>> res, List<Integer> path) {
path.add(root.val);
if (root.left == null & root.right == null) {
if (targetSum - root.val == 0) {
res.add(new ArrayList<>(path));
}
return;
}
if (root.left != null) {
dfs(root.left, targetSum - root.val, res, path);
path.remove(path.size() - 1);
}
if (root.right != null) {
dfs(root.right, targetSum - root.val, res, path);
path.remove(path.size() - 1);
}
}
}题目 ：106. 从中序与后序遍历序列构造二叉树
思路
首先回忆一下如何根据两个顺序构造一个唯一的二叉树，相信理论知识大家应该都清楚，就是以 后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。
如果让我们肉眼看两个序列，画一棵二叉树的话，应该分分钟都可以画出来。
流程如图：
那么代码应该怎么写呢？
说到一层一层切割，就应该想到了递归。
来看一下一共分几步：
第一步：如果数组大小为零的话，说明是空节点了。
第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
第五步：切割后序数组，切成后序左数组和后序右数组
第六步：递归处理左区间和右区间
难点大家应该发现了，就是如何切割，以及边界值找不好很容易乱套。
此时应该注意确定切割的标准，是左闭右开，还有左开右闭，还是左闭右闭，这个就是不变量，要在递归中保持这个不变量。
在切割的过程中会产生四个区间，把握不好不变量的话，一会左闭右开，一会左闭右闭，必然乱套！
首先要切割中序数组，为什么先切割中序数组呢？
切割点在后序数组的最后一个元素，就是用这个元素来切割中序数组的，所以必要先切割中序数组。
后序数组的切割点怎么找？
后序数组没有明确的切割元素来进行左右切割，不像中序数组有明确的切割点，切割点左右分开就可以了。
此时有一个很重的点，就是中序数组大小一定是和后序数组的大小相同的（这是必然）。
中序数组我们都切成了左中序数组和右中序数组了，那么后序数组就可以按照左中序数组的大小来切割，切成左后序数组和右后序数组。
题解
class Solution {
Map<Integer, Integer> map; // 方便根据数值查找位置
public TreeNode buildTree(int[] inorder, int[] postorder) {
map = new HashMap<>();
// 用map保存中序序列的数值对应位置
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
// 前闭后开
return findNode(inorder, 0, inorder.length, postorder,0, postorder.length);
}
public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
// 参数里的范围都是前闭后开
if (inBegin >= inEnd || postBegin >= postEnd) {
// 不满足左闭右开，说明没有元素，返回空树
return null;
}
// 找到后序遍历的最后一个元素在中序遍历中的位置
int rootIndex = map.get(postorder[postEnd - 1]);
TreeNode root = new TreeNode(inorder[rootIndex]); // 构造结点
// 保存中序左子树个数，用来确定后序数列的个数
int lenOfLeft = rootIndex - inBegin;
root.left = findNode(inorder, inBegin, rootIndex,
postorder, postBegin, postBegin + lenOfLeft);
root.right = findNode(inorder, rootIndex + 1, inEnd,
postorder, postBegin + lenOfLeft, postEnd - 1);
return root;
}
}前序和中序可以唯一确定一棵二叉树。
后序和中序可以唯一确定一棵二叉树。
那么前序和后序可不可以唯一确定一棵二叉树呢？
前序和后序不能唯一确定一棵二叉树！，因为没有中序遍历无法确定左右部分，也就是无法分割。