代码随想录算法刷题训练营day19：LeetCode(404)左叶子之和、LeetCode(112)路径总和、LeetCode(113)路径总和 II、LeetCode(105)从前序与中序遍历序列构造二叉树、LeetCode(106)从中序与后序遍历序列构造二叉树
LeetCode(404)左叶子之和
题目
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
//int sum=0;
//递归条件变化一下
if(root==null){
return 0;
}
if(root.left==null&&root.right==null){
return 0;
}
//int sum=0;
int result=sumOfLeftLeavesTest(root);
return result;
}
public int sumOfLeftLeavesTest(TreeNode root){
if(root==null){
return 0;
}
if(root.left==null&&root.right==null){
return 0;
}
int leftSum=sumOfLeftLeavesTest(root.left);//此时是左子树，同样也是叶子节点
int rightSum=sumOfLeftLeavesTest(root.right);
int leftValue=0;
if(root.left!=null&&root.left.left==null&&root.left.right==null){
//空指针异常问题
leftValue=root.left.val;
}
int sum=leftSum+rightSum+leftValue;
return sum;
}
}
LeetCode(112)路径总和
题目
代码
import java.util.ArrayList;
import java.util.List;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
//采用前序遍历，把二叉树的所有路径取出来，放到集合通过遍历集合读出路径和
List<List> pathDate=new ArrayList<>();
List<Integer> paths=new ArrayList<>();
//定义一个获取路径的函数
getPaths(root,pathDate,paths);
for(int i=0;i<pathDate.size();i++){
List<Integer> path=pathDate.get(i);
int sum=0;
for(int j=0;j<path.size();j++){
sum=sum+path.get(j);
}
if(sum==targetSum){
return true;
}
}
return false;
}
public void getPaths(TreeNode root,List<List> pathDate,List<Integer> paths){
//设置终止条件
if(root==null){
return;
}
//前序遍历----到根节点进行判断---不然如果仅有一个节点，加入不了根结点数据
paths.add(root.val);
//判断到叶子节点的时候，将存储的路径数据放到集合里面
if(root.left==null&&root.right==null){
//将路径存储到pathDate中
List<Integer> date = new ArrayList<>();
date.addAll(paths);//拷贝数据----引用型数据不能直接赋值
pathDate.add(date);
}
//遍历左子树
if(root.left!=null){
getPaths(root.left, pathDate, paths);
//回溯
paths.remove(paths.size()-1);
}
//遍历右子树
if(root.right!=null){
getPaths(root.right, pathDate, paths);
//回溯
paths.remove(paths.size()-1);
}
}
}
LeetCode(113)路径总和 II
题目
代码
import java.util.ArrayList;
import java.util.List;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List> datePath=new ArrayList<>();//存放所有路径数据
List<Integer> paths=new ArrayList<>();//存放遍历路径数据
List<List<Integer>> resultPath=new ArrayList<>();//存放结果路径数据
getTreePath(root,datePath,paths);
for(int i=0;i<datePath.size();i++){
List<Integer> path=new ArrayList<>();
path=datePath.get(i);
int sum=0;
for(int j=0;j<path.size();j++){
sum=sum+path.get(j);
}
if(sum==targetSum){
resultPath.add(path);
}
}
return resultPath;
}
//定义获取树路径的函数
public void getTreePath(TreeNode root,List<List> datePath,List<Integer> paths){
if(root==null){
return;//终止条件1---防止空节点异常
}
//收尾路径----先通过先序遍历
paths.add(root.val);//遍历根节点，保证有数据
if(root.left==null&&root.right==null){
List<Integer> data=new ArrayList<>();
data.addAll(paths);
datePath.add(data);
}
//遍历左子树
if(root.left!=null){
getTreePath(root.left, datePath, paths);
//回溯
paths.remove(paths.size()-1);
}
//遍历右子树
if(root.right!=null){
getTreePath(root.right, datePath, paths);
//回溯
paths.remove(paths.size()-1);
}
}
}
LeetCode(105)从前序与中序遍历序列构造二叉树
题目
代码
import java.util.Arrays;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
//切割+递归
//终止条件
if(preorder.length==0){
return null;
}
//取根节点
int rootdate=preorder[0];
TreeNode root=new TreeNode(rootdate);
int index=0;
//找出中序遍历数组的中间节点
for (int i = 0; i < inorder.length; i++) {
if(rootdate==inorder[i]){
index=i;
}
}
//切割中序
int[] leftInorder=Arrays.copyOfRange(inorder, 0, index);
int[] rightInorder=Arrays.copyOfRange(inorder, index+1, inorder.length);
//切割后续
int dateLength=leftInorder.length;
int[] leftPreorder=Arrays.copyOfRange(preorder, 1, 1+dateLength);
int[] rightPreorder=Arrays.copyOfRange(preorder, 1+dateLength, preorder.length);
//继续递归
root.left=buildTree(leftPreorder, leftInorder);
root.right=buildTree(rightPreorder, rightInorder);
return root;
}
}
LeetCode(106)从中序与后序遍历序列构造二叉树
题目
代码
import java.util.Arrays;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
//方法：进行切割中序和后序
//判断树是否为空树
if(inorder.length==0){
return null;//终止条件
}
//后序遍历数组的最后一个数字是根节点
//把根节点高处来，便于切割中序数组和中序数组
//递归终止条件
int index=0;
TreeNode root=new TreeNode();
int indexRoot=postorder[postorder.length-1];
/* if(postorder.length>0){//设置
root.val=indexRoot;
//切割中序数组
} */
root.val=indexRoot;
for (int i = 0; i < inorder.length; i++) {
if(indexRoot==inorder[i]){
index=i;
break;
}
}
//获取中间索引位置
//获取中序遍历中左子树的中序遍历
int[] leftInorder=Arrays.copyOfRange(inorder, 0, index);
int[] rightInorder=Arrays.copyOfRange(inorder, index+1, inorder.length);
//切割后序遍历数组
int leftLength=leftInorder.length;
int[] leftPostorder=Arrays.copyOfRange(postorder, 0, leftLength);
int[] rightPostorder=Arrays.copyOfRange(postorder, leftLength, postorder.length-1);//根据下标截取数组
//递归开始，将左子树，仍进去
root.left=buildTree(leftInorder, leftPostorder);
root.right=buildTree(rightInorder, rightPostorder);
return root;
}
}
