LeetCode hot 100 解题思路记录（二）
前情提要
本文是个人学习的粗糙笔记，仅记录思路和图解（跳过了困难题，等之后再弄）
视频看的是油管上的neetcode
二叉树
二叉树的中序遍历（简单）
中序遍历：访问顺序为左子树 → 根节点 → 右子树
思路一：迭代，遍历+栈
列表和栈初始化、将当前节点所有左子节点入栈、弹出栈顶节点记录值、转到右子树
左、中、右
思路二：Morris中序遍历（不想看，问问是否要多个思路来考核再来看）
代码实现用的是遍历+栈的思路
class Solution { public List<Integer> inorderTraversal(TreeNode root) { //初始化 List<Integer> ans = new ArrayList<>(); Deque<TreeNode> stk = new LinkedList<>(); //左节点入栈 while(root!=null || !stk.isEmpty()){//为什么用||而不是&&呢？只要还有左子树要处理、只要栈中还有待处理的节点，就还有节点要处理就得继续循环 while(root!=null){ stk.push(root); root=root.left; } root=stk.pop();//左节点出栈 ans.add(root.val);//保存左节点、中节点，有些节点是同时兼顾左节点和中节点角色 root=root.right;//保存右节点 } return ans; } }二叉树的最大深度（简单）
思路一：深度优先搜索DFS
思路二：广度优先搜索BFS
代码实现用的是深度优先搜索DFS，从底向上统计，递归
class Solution { public int maxDepth(TreeNode root) { if(root==null){ return 0; } int L=maxDepth(root.left); int R=maxDepth(root.right); int ans=Math.max(L,R)+1; return ans; } }翻转二叉树（简单）
思路：从下往上进行左右子树的翻转，用递归算法
class Solution { public TreeNode invertTree(TreeNode root) { if(root==null){//这个判断很重要，是递归的终止条件 return null; } TreeNode L=invertTree(root.left); TreeNode R=invertTree(root.right); root.left=R; root.right=L; return root; } }对称二叉树（简单）
算法一：递归，双指针
p指针和q指针，最开始都指向树的根节点，随后p指针右移则q指针左移，p指针左移则q指针右移
代码步骤：函数包含，root拆解成left和right的参数
特殊情况，左右节点是否为null的判断
返回判断，左右节点值相等？左节点的左子节点与右节点的右子节点值相等？
左节点的右子节点与右节点的左子节点相等？
class Solution { public boolean isSymmetric(TreeNode root) { return checked(root.right,root.left); } public boolean checked(TreeNode L, TreeNode R){ if(L==null && R ==null){//检查是否两个都为空 return true; } if(L==null || R==null){//检查是否一个为空一个非空 return false; } return L.val==R.val && checked(L.left,R.right) && checked(R.left, L.right); } }用p和q指针比较好，用L和R有点绕。。。
算法二：迭代，队列
根节点初始化时加入队列两次
每次提取两个节点，比较值，再比较两节点的左右子节点的值(注意顺序)
当队列为空或检测到值不等时结束
二叉树的直径（简单）
递归，左子树深度+右子树深度
代码步骤：变量ans、主函数
depth函数，特殊情况判断、左子树右子树递归、直径最大值保存、以该节点为根的子树深度
class Solution { int ans=0; public int diameterOfBinaryTree(TreeNode root) { //diameterof(root.left,root.right); depth(root); return ans; } public int depth(TreeNode node){ if(node==null){ return 0; } int L=depth(node.left); int R=depth(node.right); ans=Math.max(L+R,ans); return Math.max(L,R)+1; } }二叉树的层序遍历
广度优先搜索BFS
结果列表、层列表、queue
代码步骤：初始化 ，结果列表、特殊情况判断
queue、放root进队列
处理queue里的值，初始化层列表、queue的大小
node、node.left、node.right、层列表
//写一下思路 //结果列表、层列表、列表 //初始化结果列表，特殊情况判断 //初始化列表，root入队 //循环 层列表初始化 层列表大小 node出队到层列表中，node的左右子节点入队 class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ans=new ArrayList<>(); if(root==null){ return ans; } //Queue<TreeNode> queue= new ArrayQueue<>(); Queue<TreeNode> queue= new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ List<Integer> level= new ArrayList<>(); int sizeofLevel=queue.size(); for(int i=1;i<=sizeofLevel;i++){ //TreeNode node= queue.pop(); TreeNode node= queue.poll(); level.add(node.val); if(node.left!=null){ queue.offer(node.left); } if(node.right!=null){ queue.offer(node.right); } } ans.add(level); } return ans; } }offer(e)：将元素加入队列尾部（FIFO顺序）。poll()：从队列头部移除并返回元素。push(e)：将元素压入栈顶（即链表头部，LIFO顺序）。pop()：从栈顶（头部）移除并返回元素。Deque<TreeNode> queue = new LinkedList<>(); // 声明为 Deque，但当作队列用
Deque<TreeNode> stack = new LinkedList<>(); // 声明为 Deque，但当作栈用
有序数组转换为二叉搜索树(简单）
知识点：平衡二叉树，左节点<根节点<右节点
思路：中序遍历，选择中间位置左边/右边/任意一边为根节点
int mid = (left + right) / 2;int mid = (left + right + 1) / 2;int mid = (left + right + rand.nextInt(2)) / 2;代码步骤：
取中点：选当前区间中间位置的值作为根节点
递归左右：
左子树 = 左边区间（
left到mid-1）右子树 = 右边区间（
mid+1到right）
终止条件：当
left > right时返回null
class Solution { public TreeNode sortedArrayToBST(int[] nums) { return helper(nums,0,nums.length-1); } public TreeNode helper(int[] nums, int left,int right){ if(left>right){ return null; } int mid=(left+right)/2; TreeNode root = new TreeNode(nums[mid]); root.left=helper(nums,left,mid-1); root.right=helper(nums,mid+1,right); return root; } }验证二叉搜索树
5<4, 所以不能只比较相邻左右子节点
比较时有左右边界
代码实现：中序遍历
class Solution { public boolean isValidBST(TreeNode root) { //Queue<TreeNode> queue= new ArrayQueue<>(); Deque<TreeNode> stack= new LinkedList<>(); double inorder = -Double.MAX_VALUE; while(root!=null || !stack.isEmpty()){ while(root!=null){ stack.push(root); root=root.left; } root=stack.pop();