代码随想录第十六天| 513.找树左下角的值 、112. 路径总和 、113. 路径总和 II、106、从中序与后序遍历序列构造二叉树
513. 找树左下角的值
题目描述
给定一个二叉树，找到树的最后一行最左边的节点值。
解题思路
- 深度优先遍历 (DFS)：使用深度优先遍历来查找树的左下角值。
- 记录最大深度：定义
maxDepth变量，用于记录遍历时的最大深度。 - 更新左下角节点值：在每次到达叶子节点时，判断当前深度是否大于
maxDepth，如果是，则更新maxDepth和结果result，保存当前节点值为最左下角的节点值。 - 回溯：在递归中回溯深度值
depth，避免对其他分支的影响。
代码实现
class Solution {
public int maxDepth = -1;
int result;
public int findBottomLeftValue(TreeNode root) {
traversal(root,0);
return result;
}
public void traversal(TreeNode root,int depth) {
if(root.left == null && root.right==null){
if(depth>maxDepth){
maxDepth = depth;
result = root.val;
}
}
if(root.left != null){
depth++;
traversal(root.left,depth);
depth--;
}
if(root.right != null){
depth++;
traversal(root.right,depth);
depth--;
}
}
}
- 路径总和
112. 路径总和
题目描述
给定一个二叉树和一个目标和 targetSum，判断该树中是否存在一条从根节点到叶子节点的路径，使得路径上所有节点值的和等于目标和。
解题思路
- 递归减去节点值：每次递归进入一个节点时，将当前节点值从
targetSum中减去。 - 判断叶子节点：当到达叶子节点时，如果
targetSum减到0，说明找到了符合条件的路径，返回true。 - 左右子树递归：如果当前节点不是叶子节点，递归地检查其左右子树是否存在满足条件的路径。
- 短路逻辑：在递归过程中，如果找到符合条件的路径，立即返回
true，否则最终返回false。
代码实现
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
targetSum -= root.val;
if(root.left == null && root.right == null && targetSum ==0){
return true;
}
if(root.left == null && root.right == null && targetSum !=0){
return false;
}
if(root.left != null){
boolean left = hasPathSum(root.left,targetSum);
if(left)return left;
}
if(root.right != null){
boolean right = hasPathSum(root.right,targetSum);
if(right)return right;
}
return false;
}
}
113. 路径总和 II
题目描述
给定二叉树的根节点 root 和一个整数目标和 targetSum，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
解题思路
- 递归深度优先遍历：使用递归的深度优先搜索 (DFS) 来遍历二叉树，从根节点开始，到达叶子节点。
- 路径存储：在遍历的过程中使用
path列表保存当前路径中的节点。 - 判断叶子节点：每当到达叶子节点时，判断当前路径总和是否等于
targetSum。如果满足条件，将当前路径的一个拷贝添加到结果res中。 - 回溯：每次递归返回上层节点时，移除
path中的最后一个节点，确保在遍历其他路径时路径正确。
代码实现
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetsum) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root==null){
return res;
}
List<Integer> path = new LinkedList<>();
preorderdfs(root, targetsum, res, path);
return res;
}
public void preorderdfs(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){
preorderdfs(root.left,targetsum-root.val, res, path);
path.remove(path.size()-1);
}
if(root.right != null){
preorderdfs(root.right,targetsum-root.val, res, path);
path.remove(path.size()-1);
}
}
}
106. 从中序与后序遍历序列构造二叉树
题目：根据一棵树的中序遍历与后序遍历构造二叉树。
注意：你可以假设树中没有重复的元素。
解题思路：
- 后序遍历的最后一个元素是树的根节点。
- 在中序遍历中找到根节点位置，从而分割出左右子树的中序序列。
- 根据左右子树的大小，在后序序列中划分出左右子树的后序序列。
- 递归构造左右子树，直至构造完成。
代码：
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(postorder.length == 0 || inorder.length==0){
return null;
}
return bulidHelper(inorder,0,inorder.length,postorder,0,postorder.length);
}
private TreeNode bulidHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd){
if(postorderStart==postorderEnd){
return null;
}
int rootVal = postorder[postorderEnd-1];
TreeNode root = new TreeNode(rootVal);
int middleIndex;
for(middleIndex=inorderStart;middleIndex<inorderEnd;middleIndex++){
if(inorder[middleIndex]==rootVal)
break;
}
int leftinorderStart = inorderStart;
int leftinorderEnd = middleIndex;
int leftpostorderStart = postorderStart;
int leftpostorderEnd = postorderStart+middleIndex-inorderStart;
int rightinorderStart = middleIndex+1;
int rightinorderEnd = inorderEnd;
int rightpostorderStart = postorderStart+middleIndex-inorderStart;
int rightpostorderEnd = postorderEnd-1;
root.left = bulidHelper(inorder,leftinorderStart,leftinorderEnd,postorder,leftpostorderStart,leftpostorderEnd);
root.right = bulidHelper(inorder,rightinorderStart,rightinorderEnd,postorder,rightpostorderStart,rightpostorderEnd);
return root;
}
}
105.从前序与中序遍历序列构造二叉树
题目：根据一棵树的中序遍历与前序遍历构造二叉树。
注意：你可以假设树中没有重复的元素。
解题思路：
- 后序遍历的最后一个元素是树的根节点。
- 在中序遍历中找到根节点位置，从而分割出左右子树的中序序列。
- 根据左右子树的大小，在后序序列中划分出左右子树的后序序列。
- 递归构造左右子树，直至构造完成。
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length == 0 || inorder.length ==0){
return null;
}
return helper(preorder,0,preorder.length, inorder,0,inorder.length);
}
private TreeNode helper(int[] preorder,int preorderstart,int preorderend, int[] inorder,int inorderstart,int inorderend){
if(preorderstart == preorderend){
return null;
}
int rootval = preorder[preorderstart];
TreeNode root =new TreeNode(rootval);
int midval;
for(midval = inorderstart;midval<inorderend;midval++){
if(inorder[midval]==rootval)
break;
}
int leftpreorderstart = preorderstart+1;
int leftpreorderend = preorderstart+midval-inorderstart+1;
int leftinorderstart = inorderstart;
int leftinorderend = midval;
int rightpreorderstart = preorderstart+midval-inorderstart+1;
int rightpreorderend = preorderend;
int rightinorderstart = midval+1;
int rightinorderend = inorderend;
root.left = helper(preorder,leftpreorderstart,leftpreorderend, inorder,leftinorderstart,leftinorderend);
root.right = helper(preorder,rightpreorderstart,rightpreorderend, inorder,rightinorderstart,rightinorderend);
return root;
}
}