105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 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 <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder和inorder均 无重复 元素inorder均出现在preorderpreorder保证 为二叉树的前序遍历序列inorder保证 为二叉树的中序遍历序列
/**
* 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 Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
public TreeNode dealTree(int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft, int inRight) {
if (preLeft > preRight || inLeft > inRight) {
return null;
}
// 当前节点的下标就是先序的第一个，也就是左边界preLeft
int nowPreIndex = preLeft;
// 那么当前节点，在中序遍历的下标是哪里呢？通过映射关系去找
int nowInIndex = indexMap.get(preorder[nowPreIndex]);
// 计算一下，在本节点的左边的数据到底有多少，右边又有多少
int numLeft = nowInIndex - inLeft; // 通过当前下标减左边界下标得到
// 好，两边的下标都找到了，就不管了，开始处理本节点的事情
TreeNode now = new TreeNode(preorder[nowPreIndex]);
// 然后为他创建左右字数的内容
// 边界改变，前序左边界去掉了本节点，前序右边界也无需递归那么多（看到底再本节点的左边有多少），然后是前序左边界，到当前下标-1
now.left = dealTree(preorder, inorder, preLeft + 1, preLeft + numLeft, inLeft, nowInIndex - 1);
now.right = dealTree(preorder, inorder, preLeft + numLeft + 1, preRight, nowInIndex + 1, inRight);
return now;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
// 通过中序遍历，创建对应的映射下标关系（可以快速分辨出对应的节点，是在当前节点的左边还是右边）
int num = inorder.length;
for (int i = 0; i < num; i++) {
indexMap.put(inorder[i], i);
}
return dealTree(preorder, inorder, 0, num - 1, 0, num - 1);
}
}437. 路径总和 III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3提示:
- 二叉树的节点个数的范围是
[0,1000] -109 <= Node.val <= 109-1000 <= targetSum <= 1000
/**
* 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 pathSum(TreeNode root, long targetSum) {
if (root == null) {
return 0;
}
int ret = rootSum(root, targetSum);
ret += pathSum(root.left, targetSum);
ret += pathSum(root.right, targetSum);
return ret;
}
public int rootSum(TreeNode root, long targetSum) {
int ret = 0;
if (root == null) {
return 0;
}
int val = root.val;
if (val == targetSum) {
ret++;
}
ret += rootSum(root.left, targetSum - val);
ret += rootSum(root.right, targetSum - val);
return ret;
}
}
