代码随想录算法训练营day18 | 题目513、题目112、题目113、题目106、题目105、题目889
题目一描述
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3]
输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
提示:
二叉树的节点个数的范围是 [1,10^4]
-2^31 <= Node.val <= 2^31 - 1
解题思路
bfs，层序遍历，先右后左，得到最后一个结点即可。
dfs，需要一个全局变量标定最深的结点，先左后右dfs，每次更新最深层的时候，也就是当前最底层最左边的那个节点。
代码实现
方法一：
class Solution {
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
TreeNode temp = new TreeNode();
while (!queue.isEmpty()) {
temp = queue.poll();
if (temp.right != null) {
queue.offer(temp.right);
}
if (temp.left != null) {
queue.offer(temp.left);
}
}
return temp.val;
}
}
方法二：
class Solution {
int res = 0;
int resLayer = -1;
public int findBottomLeftValue(TreeNode root) {
dfs(root, 0);
return res;
}
private void dfs(TreeNode root, int layer) {
if (root == null)
return;
if(resLayer < layer){
resLayer = layer;
res = root.val;
}
dfs(root.left, layer + 1);
dfs(root.right, layer + 1);
}
}
题目二描述
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。
提示：
树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
解题思路
dfs，bfs均可，将path信息同步回溯即可。
代码实现
方法一：
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
int curSum = 0;
return dfs(root, curSum, targetSum);
}
private boolean dfs(TreeNode root, int curSum, int targetSum) {
if (root == null) {
return false;
}
curSum += root.val;
if (root.left == null && root.right == null) {
return curSum == targetSum;
}
return dfs(root.left, curSum, targetSum) || dfs(root.right, curSum, targetSum);
}
}
方法二：
class MyTreeNode {
TreeNode root;
int curSum;
MyTreeNode(TreeNode root, int curSum) {
this.root = root;
this.curSum = curSum;
}
}
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null)
return false;
Queue<MyTreeNode> queue = new ArrayDeque<>();
queue.offer(new MyTreeNode(root, root.val));
while (!queue.isEmpty()) {
MyTreeNode temp = queue.poll();
int curSum = temp.curSum;
if (temp.root.left == null && temp.root.right == null) {
if (curSum == targetSum)
return true;
}
if (temp.root.left != null) {
queue.offer(new MyTreeNode(temp.root.left, temp.curSum + temp.root.left.val));
}
if (temp.root.right != null) {
queue.offer(new MyTreeNode(temp.root.right, temp.curSum + temp.root.right.val));
}
}
return false;
}
}
技巧总结
自定义类来将信息同步出入队列
题目三描述
113. 路径总和 II
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：[]
示例 3：
输入：root = [1,2], targetSum = 0
输出：[]
提示：
树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
解题思路
dfs，传递并回溯path信息即可，注意如果每次进入新的结点都复制新的path会很慢，可以使用remove来回溯。
也要注意如果用上法，在加入结果集的时候一定要复制，不然在后面remove的时候也会修改掉res中的path数据。
bfs需要同步记录sum和path
代码实现
方法一：
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if (root == null)
return res;
List<Integer> path = new LinkedList<>();
dfs(root, path, targetSum);
return res;
}
private void dfs(TreeNode root, List<Integer> path, int targetSum) {
if (root == null)
return;
path.add(root.val);
targetSum -= root.val;
if (root.left == null && root.right == null) {
if (targetSum == 0) {
res.add(new LinkedList<>(path));
}
}
// dfs(root.left, new LinkedList(path), targetSum);
// dfs(root.right, new LinkedList(path), targetSum);
dfs(root.left, path, targetSum);
dfs(root.right, path, targetSum);
path.remove(path.size()-1);
}
}
方法二：
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> res = new ArrayList<>();
if (root == null)
return res;
Queue<TreeNode> queue = new ArrayDeque<>();
Queue<List<Integer>> path = new ArrayDeque<>();
Queue<Integer> sum = new ArrayDeque<>();
queue.offer(root);
// path.offer(new ArrayList<>(root.val));
List<Integer> rootPath = new ArrayList<>();
rootPath.add(root.val);
path.offer(rootPath);
sum.offer(root.val);
while (!queue.isEmpty()) {
TreeNode temp = queue.poll();
List<Integer> curPath = path.poll();
int curSum = sum.poll();
if (temp.left == null && temp.right == null && curSum == targetSum) {
res.add(curPath);
}
if (temp.left != null) {
queue.offer(temp.left);
sum.offer(temp.left.val + curSum);
List<Integer> leftPath = new ArrayList<>(curPath);
leftPath.add(temp.left.val);
path.offer(leftPath);
}
if (temp.right != null) {
queue.offer(temp.right);
sum.offer(temp.right.val + curSum);
List<Integer> rightPath = new ArrayList<>(curPath);
rightPath.add(temp.right.val);
path.offer(rightPath);
}
}
return res;
}
}
技巧总结
学会list的remove方法。
注意加入结果集时要复制，复制要带<>，
注意 new ArrayList<>()的方法只能接受一个集合类初始化，直接传入int是不行的。
注意 rootPath.add(root.val);返回值是布尔类型，不能直接传入给offer方法。
注意学会ArrayList的初始化和offer的接受类型。
题目四描述
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
示例 2:
输入：inorder = [-1], postorder = [-1]
输出：[-1]
提示:
1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由 不同 的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历
解题思路
当前结点值是后续遍历第一位
根据上一步的值在中序找到位置，分割中序的左右子树
根据上一步的左右子树长度，在后序中切割左右子树
递归左子树，返回左子树的头结点为左孩子连接到当前结点
递归右子树
代码实现
方法一：
class Solution {
Map<Integer, Integer> map = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return build(inorder, 0, inorder.length, postorder, 0, postorder.length);
}
private TreeNode build(int[] inorder, int inStart, int inEnd,
int[] postorder, int postStart, int postEnd) {
// 当前结点值是后续遍历第一位
// 根据上一步的值在中序找到位置，分割中序的左右子树
// 根据上一步的左右子树长度，在后序中切割左右子树
// 递归左子树，返回左子树的头结点为左孩子连接到当前结点
// 递归右子树
if (inStart >= inEnd || postStart >= postEnd) {
return null;
}
TreeNode res = new TreeNode(postorder[postEnd - 1]);
int rootIndex = map.get(res.val);
int leftInStart = inStart;
int leftInEnd = rootIndex;
int rightInStart = leftInEnd + 1;
int rightInEnd = inEnd;
int leftPostStart = postStart;
int leftPostEnd = leftPostStart + leftInEnd - leftInStart;
int rightPostStart = leftPostEnd;
int rightPostEnd = postEnd - 1;
res.left = build(inorder, leftInStart, leftInEnd,
postorder, leftPostStart, leftPostEnd);
res.right = build(inorder, rightInStart, rightInEnd,
postorder, rightPostStart, rightPostEnd);
return res;
}
}
题目五描述
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
提示:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列
解题思路
一样的根据前序来获得当前结点值，根据中序来划分左右子树，得到左右子树长度再去前序里分割数组。
代码实现
方法一：
class Solution {
Map<Integer, Integer> map = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return build(preorder, 0, preorder.length,
inorder, 0, inorder.length);
}
public TreeNode build(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd) {
if (preStart >= preEnd)
return null;
TreeNode res = new TreeNode(preorder[preStart]);
int rootIndex = map.get(res.val);
int leftInStart = inStart;
int leftInEnd = rootIndex;
int rightInStart = rootIndex + 1;
int rightInEnd = inEnd;
int leftPreStart = preStart + 1;
int leftPreEnd = leftPreStart + leftInEnd - leftInStart;
int rightPreStart = leftPreEnd;
int rightPreEnd = preEnd;
res.left = build(preorder, leftPreStart, leftPreEnd, inorder, leftInStart, leftInEnd);
res.right = build(preorder, rightPreStart, rightPreEnd, inorder, rightInStart, rightInEnd);
return res;
}
}
题目六描述
给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。
如果存在多个答案，您可以返回其中 任何 一个。
示例 1：
输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]
示例 2:
输入: preorder = [1], postorder = [1]
输出: [1]
提示：
1 <= preorder.length <= 30
1 <= preorder[i] <= preorder.length
preorder 中所有值都 不同
postorder.length == preorder.length
1 <= postorder[i] <= postorder.length
postorder 中所有值都 不同
保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历
解题思路
根据前序得到当前结点
根据前序得到当前结点的左子树结点
根据左子树结点划分后序
根据后序长度划分前序
代码实现
方法一：
class Solution {
Map<Integer, Integer> map;
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
map = new HashMap<>();
for (int i = 0; i < postorder.length; i++) {
map.put(postorder[i], i);
}
return build(preorder, 0, preorder.length,
postorder, 0, postorder.length);
}
private TreeNode build(int[] preorder, int preStart, int preEnd,
int[] postorder, int postStart, int postEnd) {
if (preStart >= preEnd) {
return null;
}
TreeNode res = new TreeNode(preorder[preStart]);
if (preStart == preEnd - 1) {
return res;
}
int leftValue = preorder[preStart + 1];
int leftIndex = map.get(leftValue);
int leftNum = leftIndex - postStart + 1;
int leftPreStart = preStart + 1;
int leftPreEnd = preStart + leftNum + 1;
int rightPreStart = leftPreEnd;
int rightPreEnd = preEnd;
int leftPostStart = postStart;
int leftPostEnd = postStart + leftNum;
int rightPostStart = leftPostEnd;
int rightPostEnd = postEnd - 1;
res.left = build(preorder, leftPreStart, leftPreEnd,
postorder, leftPostStart, leftPostEnd);
res.right = build(preorder, rightPreStart, rightPreEnd,
postorder, rightPostStart, rightPostEnd);
return res;
}
}
