LeetCode hot 100 解题思路记录（二）

前情提要本文是个人学习的粗糙笔记，仅记录思路和图解（跳过了困难题，等之后再弄）视频看的是油管上的neetcode二叉树二叉树的中序遍历（简单）中序遍历：访问顺序为左子树 → 根节点 → 右子树思路一：迭代，遍历+栈 列表和栈初始化、将当前节点所有左子节点入栈、弹出栈顶节点记录值、转到右子树 左、中、右思路二：Morris中序遍历（不想看，问问是否要多个思路来考核再来看）代码实现用的是遍历+栈的思路class Solution { public ListInteger inorderTraversal(TreeNode root) { //初始化 ListInteger ans = new ArrayList(); DequeTreeNode 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 ListListInteger levelOrder(TreeNode root) { ListListInteger ans=new ArrayList(); if(root==null){ return ans; } //QueueTreeNode queue= new ArrayQueue(); QueueTreeNode queue= new LinkedList(); queue.offer(root); while(!queue.isEmpty()){ ListInteger 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()：从栈顶（头部）移除并返回元素。DequeTreeNode queue = new LinkedList(); // 声明为 Deque，但当作队列用DequeTreeNode 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时返回nullclass Solution { public TreeNode sortedArrayToBST(int[] nums) { return helper(nums,0,nums.length-1); } public TreeNode helper(int[] nums, int left,int right){ if(leftright){ 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; } }验证二叉搜索树54, 所以不能只比较相邻左右子节点比较时有左右边界代码实现：中序遍历class Solution { public boolean isValidBST(TreeNode root) { //QueueTreeNode queue= new ArrayQueue(); DequeTreeNode 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();