力扣-Hot100-二叉树其二【算法学习day.33】

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.从前序和中序遍历序列构造二叉树

题目链接:105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

题面:

基本分析:前序遍历数组中第一个是头结点，头结点在中序遍历数组中的位置为1,1之前的节点都属于头结点的左子树节点，1之后的节点都属于头结点的右子树节点，根据此规律递归下去

代码:

java">/*** 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) {TreeNode root =  recursion(preorder,0,preorder.length-1,inorder,0,inorder.length-1);return root;}public TreeNode recursion(int[] preorder,int prestart,int preend, int[] inorder,int instart,int inend){if(prestart>preend)return null;int rootval = preorder[prestart];TreeNode root = new TreeNode(rootval);int index = 0;for(int i = instart;i<=inend;i++){if(inorder[i]==rootval){index = i;break;}}int leftnum = index - instart;root.left = recursion(preorder,prestart+1,prestart+leftnum,inorder,instart,instart+leftnum-1);root.right = recursion(preorder,prestart+leftnum+1,preend,inorder,instart+leftnum+1,inend);return root;}
}

2. 路径总和III

题目链接:437. 路径总和 III - 力扣（LeetCode）

题面:

基本分析:利用dfs暴力，力扣题解中也有大佬使用前缀和，推荐看一下

代码:

java">/*** 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 {int ans = 0;int targetSum;public int pathSum(TreeNode root, int targetSum) {if(root==null)return 0;this.targetSum=targetSum;recursion(root);return ans;}public void recursion(TreeNode root){if(root==null){return;}recursion2(root,root.val);recursion(root.left);recursion(root.right);}public void recursion2(TreeNode root,long val){if(val==targetSum)ans++;if(root.left!=null)recursion2(root.left,val+root.left.val);if(root.right!=null)recursion2(root.right,val+root.right.val);}
}

3.二叉树中的最大路径和

题目链接:124. 二叉树中的最大路径和 - 力扣（LeetCode）

题面:

基本分析：dp

代码:

java">/*** 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 {private int ans = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {dfs(root);return ans;}private int dfs(TreeNode node) {if (node == null) {return 0; // 没有节点，和为 0}int lVal = dfs(node.left); // 左子树最大链和int rVal = dfs(node.right); // 右子树最大链和ans = Math.max(ans, lVal + rVal + node.val); // 两条链拼成路径return Math.max(Math.max(lVal, rVal) + node.val, 0); // 当前子树最大链和（注意这里和 0 取最大值了）}
}