106、从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
细节1：
//利用后序遍历可得后序遍历的最后一个结点为根结点 int rootValue=postorder[postEnd-1]; 不能使用postorder[postorder.length-1] 因为是递归,而每一次的根结点都会变化的,所以应该使用postEnd-1来
细节2：
//构造右子树 root.right=build(inorder, rootIndex+1, infixEnd, postorder, postStart+leftNum, postEnd-1); 这里后续遍历的右子树应该是[postStart+leftNum, postEnd-1)，而不应该是[postStart+leftNum, rootIndex) 因为中序遍历和后续遍历对应的数组里索引为数组初始和索引为数组末尾要用infixStart/postStart和infixEnd/postEnd表示
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return build(inorder, 0, inorder.length, postorder, 0, postorder.length);
}
public TreeNode build(int[] inorder, int infixStart, int infixEnd, int[]postorder, int postStart, int postEnd){
//终止条件
if(postStart==postEnd) return null ;
//利用后序遍历可得后序遍历的最后一个结点为根结点
int rootValue=postorder[postEnd-1];//不用使用postorder[postorder.length-1] 因为是递归,而每一次的根结点都会变化的,所以应该使用postEnd-1来
int rootIndex=-1;
//找到中序遍历里根结点的位置
for(int i=0;i
236、二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
为什么说找到一个就可以，因为：
1、如果q是p的子孙,那么肯定先找到的是p,那么p就是p和q的公共祖先。因为在递归的时候，会因为if(root.val==p.val||root.val==q.val)而返回p
2、如果q不是p的子孙,那么在到达p之前,肯定会先到达p和q的公共祖先r,然后分别到达p和q,也就可以返回root了
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null) return null;
if(p==null&&q==null) return root;
if(root.val==p.val||root.val==q.val) return root;
root.left=lowestCommonAncestor(root.left,p,q);
root.right=lowestCommonAncestor(root.right,p,q);
if(root.left!=null&&root.right!=null) return root;
return root.left==null?root.right:root.left;
}
}
713、乘积小于 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
跟数组有关的解法：暴力解法、双指针、滑动窗口、二分查找。-------->最后合适的只有滑动窗口
细节1：
count+=right-left+1;——>关键点。思路如下：
以数组10 5 2 6为例：当滑动窗口的右窗口扩充时，
right在10头上 移动到5头上，10×5＜100
既然10×5＜100那么5×1肯定也＜100
故滑动窗口的位置从10扩充到5有count＝2（10×5 ，5）
即right-left+1
细节2：
while(left<=right&&sum>=k)
因为right位置换到了这个while的下面，所以此while循环缩小窗口时要有left<=right来保证不能越界
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int left=0,right=0;
int sum=1,count=0;
while(right=k){
sum/=nums[left];
left++;
}
count+=right-left+1;//关键点
right++;//因为right位置换到了这里，所以上一个while循环缩小窗口时要有->left<=right
}
return count;
}
}
