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);}}