hot100（9）
81.104. 二叉树的最大深度 - 力扣（LeetCode）
后序遍历，从下往上，需要用到下面返回的结果。
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left,right) + 1;
}82.102. 二叉树的层序遍历 - 力扣（LeetCode）
层序遍历，队列
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null) return res;
level(root);
return res;
}
public void level(TreeNode root){
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while(!queue.isEmpty()){
int len = queue.size();
List<Integer> list = new ArrayList<>();
for(int i = 0 ; i < len ; i++){
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
res.add(list);
}
}83.101. 对称二叉树 - 力扣（LeetCode）
树形结构，且判断子树是否对称 与 判断原二叉树是否对称 是相同的问题，子问题与原文题具有相同的结构，考虑递归。
public boolean isSymmetric(TreeNode root) {
return isSymmetricHelper(root.left,root.right);
}
public boolean isSymmetricHelper(TreeNode p,TreeNode q){
if(p == null || q == null){
return p == q;
}
return p.val == q.val && isSymmetricHelper(p.left,q.right) && isSymmetricHelper(p.right,q.left);
}84.98. 验证二叉搜索树 - 力扣（LeetCode）
中序遍历下，输出的二叉搜索树节点的数值是有序序列。
有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。
TreeNode preNode;
public boolean isValidBST(TreeNode root) {
if(root == null) return true;
boolean left = isValidBST(root.left);
if(preNode != null && preNode.val >= root.val) return false;
preNode = root;
boolean right = isValidBST(root.right);
return left && right;
}85.96. 不同的二叉搜索树 - 力扣（LeetCode）
题解：代码随想录_不同的二叉搜索树
1.dp数组及下标含义
dp[i] : 1到i为节点组成的二叉搜索树的个数为dp[i]个
或者i个不同元素的节点组成的二叉搜索树的数量为dp[i]个
2.确定递推公式
dp[i] += dp[以j为头节点左子树节点数量]*dp[以j为头节点右子树节点数量]
j相当于是头节点的元素，从1遍历到i为止
dp[i] += dp[j-1]*dp[i-j]
3.初始化
dp[0] = 1;
从定义上来讲，空节点也是一颗二叉树，也是一科二叉搜索树，可以说得通。
同时为了满足递推公式的乘法，避免结果都为0，dp[0]需要初始化为1
4.遍历顺序
i从大到小，遍历i里每一个数作为头节点的状态，用j来遍历
5.举例推导dp数组
public int numTrees(int n) {
int[] dp = new int[n+1];
dp[0] = 1;
for(int i = 1 ; i <= n; i++){
for(int j = 1 ; j <= i ; j++){
dp[i] += (dp[j-1] * dp[i-j]);
}
}
return dp[n];
}86.94. 二叉树的中序遍历 - 力扣（LeetCode）
List<Integer> res = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
inOrder(root);
return res;
}
public void inOrder(TreeNode root){
if(root == null){
return;
}
inOrder(root.left);
res.add(root.val);
inOrder(root.right);
}87.85. 最大矩形 - 力扣（LeetCode）
题解：85.最大矩形题解 - 力扣
I暴力优化
class Solution {
public int maximalRectangle(char[][] matrix) {
int m = matrix.length;
if (m == 0) {
return 0;
}
int n = matrix[0].length;
int[][] left = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
}
}
}
int ret = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '0') {
continue;
}
int width = left[i][j];
int area = width;
for (int k = i - 1; k >= 0; k--) {
width = Math.min(width, left[k][j]);
area = Math.max(area, (i - k + 1) * width);
}
ret = Math.max(ret, area);
}
}
return ret;
}
}
单调栈
public int maximalRectangle(char[][] matrix) {
int m = matrix.length;
if(m == 0){
return 0;
}
int n = matrix[0].length;
int[][] left = new int[m][n];
for(int i = 0 ; i < m ; i++){
for(int j = 0 ; j < n ; j++){
if(matrix[i][j] == '1'){
left[i][j] = (j == 0 ? 0 : left[i][j-1]) + 1;
}
}
}
int res = 0;
for(int j = 0 ; j < n ; j++){
int[] up = new int[m];
int[] down = new int[m];
Deque<Integer> stack = new ArrayDeque<>();
for(int i = 0 ; i < m; i++){
while(!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]){
stack.pop();
}
if(stack.isEmpty()){
up[i] = -1;
}else{
up[i] = stack.peek();
}
stack.push(i);
}
stack.clear();
for(int i = m - 1 ; i >= 0 ; i--){
while(!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]){
stack.pop();
}
if(stack.isEmpty()){
down[i] = m;
}else{
down[i] = stack.peek();
}
stack.push(i);
}
for(int i = 0 ; i < m ; i++){
int height = down[i] - up[i] - 1;
int area = height * left[i][j];
res = Math.max(area,res);
}
}
return res;
}
88.84. 柱状图中最大的矩形 - 力扣（LeetCode）
单调栈
public int largestRectangleArea(int[] heights) {
int[] left = new int[heights.length];
int[] right = new int[heights.length];
int res = 0;
Deque<Integer> stack = new ArrayDeque<>();
for(int i = 0 ; i < heights.length ; i++){
while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
stack.pop();
}
left[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
stack.clear();
for(int i = heights.length - 1 ; i >= 0 ; i--){
while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
stack.pop();
}
right[i] = stack.isEmpty() ? heights.length : stack.peek();
stack.push(i);
}
for(int i = 0 ; i < heights.length ; i++){
res = Math.max((right[i] - left[i] - 1)*heights[i],res);
}
return res;
}每个元素至多进出栈一次
时间复杂度O(n) 空间复杂度O(n)
单调栈+常数优化
public int largestRectangleArea(int[] heights) {
int[] left = new int[heights.length];
int[] right = new int[heights.length];
Arrays.fill(left,-1);
Arrays.fill(right,heights.length);
int res = 0;
Deque<Integer> stack = new ArrayDeque<>();
for(int i = 0 ; i < heights.length ; i++){
while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
right[stack.peek()] = i;
stack.pop();
}
left[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
for(int i = 0 ; i < heights.length ; i++){
res = Math.max((right[i] - left[i] - 1)*heights[i],res);
}
return res;
}时间复杂度O(n) 空间复杂度(n)
89.1. 两数之和 - 力扣（LeetCode）
哈希思想，空间换时间
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0 ; i < nums.length ; i++){
int match = target - nums[i];
if(map.containsKey(match)){
res[0] = map.get(match);
res[1] = i;
return res;
}
map.put(nums[i],i);
}
return res;
}90.78. 子集 - 力扣（LeetCode）
回溯问题
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int[] nums;
public List<List<Integer>> subsets(int[] nums) {
this.nums = nums;
dfs(0);
return res;
}
public void dfs(int index){
res.add(new ArrayList<>(path));
if(index == nums.length){
return ;
}
for(int i = index ; i < nums.length ; i++){
path.add(nums[i]);
dfs(i+1);
path.remove(path.size() - 1);
}
}