LeetCode Hot100 (二叉树)

94. 二叉树的中序遍历

题意

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

题解

树的遍历分为先序遍历（先访问根节点，然后左节点，右节点），中序遍历（先访问左子树，再访问根节点，再访问右子树），后序遍历（左右根），递归的写法的话实际上就是dfs的先后顺序不同

代码

import java.util.*;public class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer>ans=new ArrayList<>();dfs(ans,root);return ans;}public  static void dfs(List<Integer> ans,TreeNode root){if(root==null){return;}dfs(ans,root.left);ans.add(root.val);dfs(ans,root.right);
//先序遍历就把ans.add放到最前面，后序遍历就放到最后面}}

104. 二叉树的最大深度

题意

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

题解

我们dfs的时候每一次都是往下一层，那么我们每一次传入的参数加1即可

代码

import java.util.*;public class Solution {// public static void main(String[] args) {// }//   public class TreeNode {//      int val;//       TreeNode left;//       TreeNode right;//       TreeNode() {}//      TreeNode(int val) { this.val = val; }//       TreeNode(int val, TreeNode left, TreeNode right) {//           this.val = val;//          this.left = left;//          this.right = right;//       }//   }public static int maxx=0;public int maxDepth(TreeNode root) {maxx=0;dfs(root,1);return maxx;}public  static void dfs(TreeNode root,int x){if(root==null){return;}maxx=Math.max(maxx,x);dfs(root.left,x+1);dfs(root.right,x+1);}}

226. 翻转二叉树

题意

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

题解

按照题意模拟即可，每一次将左右节点翻转即可

代码

import java.util.*;public class Solution {public TreeNode invertTree(TreeNode root) {dfs(root);return root;}static void dfs(TreeNode root){if(root==null){return;}TreeNode now=root.left;root.left = root.right;root.right = now;dfs(root.left);dfs(root.right);}}

101. 对称二叉树

题意

给你一个二叉树的根节点 root ， 检查它是否轴对称。

题解

递归写一下即可，我们每一次传入需要对比的是是否对称，对于顶点来说就是左右节点是否相同，那么对于他的左儿子我们定义为a，由儿子为b，实际上就是看a左是否等于b右，a右是否等于b左，下一层也是同理，实现即可

代码

import java.util.*;public class Solution {public boolean isSymmetric(TreeNode root) {return check(root.left, root.right);}static public boolean check(TreeNode rootl,TreeNode rootr){if(rootl==null&&rootr==null){return true;}if(rootl==null||rootr==null){return false;}return rootl.val==rootr.val&&check(rootl.left,rootr.right)&&check(rootl.right,rootr.left);}}

543. 二叉树的直径

题意

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

题解

如果你是acmer的话，你会发现这是一道典型的dp

我们先来看一下答案会出现在哪，是不是都是通过了某一个顶点的左边的最深的深度加上右边的最深的深度，那么我们在外部定义一个maxx值，求一下每个顶点的最大值即可，

但是我们上面有个地方需要注意，我们需要的是左边的最大深度加上右边的最大深度，所以返回的是最大的深度

代码

class Solution {public static void main(String[] args) {}static int maxx=0;public int diameterOfBinaryTree(TreeNode root) {maxx=0;dfs(root);return maxx-1;}static int  dfs(TreeNode root){if(root==null){return 0;}int l=dfs(root.left);int r=dfs(root.right);maxx=Math.max(l+r+1,maxx);return Math.max(l,r)+1;}
}

102. 二叉树的层序遍历

题意

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）

题解

一层一层向下遍历就行，queue实现，记住，每一层应当遍历完

代码

import java.util.*;public class Solution {public static void main(String[] args) {int  arr[][]={{0,1}};}public List<List<Integer>> levelOrder(TreeNode root) {Queue<TreeNode> queue=new LinkedList<>();queue.add(root);List<List<Integer>>ans=new ArrayList<>();while(queue.size()>=1){int x=queue.size();List<Integer>res=new ArrayList<>();while(x>=1){x--;TreeNode now=queue.peek();queue.poll();if(now==null){continue;}res.add(now.val);if(now==null){continue;}queue.add(now.left);queue.add(now.right);}if(res.size()==0){continue;}ans.add(res);}return ans;}}

108. 将有序数组转换为二叉搜索树

题意

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

题意

递归写，我们先来看一下什么是二叉搜索树，首先，最大深度最小深度的差值不能大于1，左子树小于根，右子树大于根，所以，我们从根开始遍历，根节点肯定是当前的数组的mid下标的值，因为要让整个二叉树的深度差值尽可能小的话左右分配要平均，那么左边就是l 到mid-1,同理，右边就是mid+1到r了，分解成两个小数组继续即可

代码

import java.util.List;class Solution {public static void main(String[] args) {int  []nums={-10,-3,0,5,9};sortedArrayToBST(nums);}public static TreeNode sortedArrayToBST(int[] nums) {TreeNode root = new TreeNode();dfs(0,nums.length-1,root,nums);return root;}public static void dfs(int l,int r,TreeNode now,int []nums){if(l>r){return;}if(l==r){now.val=nums[l];}else {int mid=(l+r)>>1;now.val=nums[mid];if(l<=mid-1){now.left=new TreeNode();dfs(l,mid-1,now.left, nums);}if(mid+1<=r){now.right=new TreeNode();dfs(mid+1,r,now.right,nums);}}}}

98. 验证二叉搜索树

题意

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

题解

也是比较简单，我们刚开始给每个节点设置一个范围l,r，因为题意的一二要求，我们每一次都把范围缩小，例如左子树本来是l到r，但以为要小于当前节点，r就改为当前节点的值即可，右边同理

代码

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;class Solution {public static void main(String[] args) {}public boolean isValidBST(TreeNode root) {Long maxx=100000000000L;Long minn=-maxx;return dfs(root,minn,maxx);}public static boolean dfs(TreeNode root,Long minn,Long maxx){if(root==null){return true;}if(root.val>=maxx||root.val<=minn){return false;}return dfs(root.right,(long)root.val,maxx)&&dfs(root.left,minn,(long)root.val );}}

230. 二叉搜索树中第 K 小的元素

题意

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

题解

还记得我们上面有一道有序数组转为二叉搜索树吗，该题也就是二叉搜索树变为有序数组，我们再来看一下二叉树的性质

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

那么我们最小的值肯定在最左的子树，那么略微大于他的肯定是他的父亲节点，那么继续呢？应该是他的父亲节点的右边的端点了，然后呢如果他还有左边的继续放入即可，这边注意一下，需要用stack来实现，因为每一次的值需要放到最上面，以及pull不可以放入null，add可以注意一下

代码

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;class Solution {public static void main(String[] args) {}public int kthSmallest(TreeNode root, int k) {Deque<TreeNode> stack = new LinkedList<TreeNode>();while (root != null || !stack.isEmpty()) {while (root != null) {stack.push(root);//push 不允许插入空值root = root.left;}root = stack.pop();--k;if (k == 0) {break;}root = root.right;}return root.val;}}

199. 二叉树的右视图

题意

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值

题解

实际上就是层序遍历取最后一个值，有疑问的同学看一下上面的102即可

代码

import java.util.*;class Solution {public static void main(String[] args) {}public List<Integer> rightSideView(TreeNode root) {List<Integer>ans=new ArrayList<>();if(root==null){return List.of();}Queue<TreeNode> dp =new LinkedList<>();dp.add(root);while(dp.size()!=0){int x=dp.size();List<Integer> arr = new ArrayList<>();while(x>=1){x--;TreeNode now=dp.poll();arr.add(now.val);if(now.left!=null){dp.add(now.left);}if(now.right!=null){dp.add(now.right);}}if(arr.size()==0){break;}ans.add(arr.get(arr.size()-1));}return ans;}}

114. 二叉树展开为链表

题意

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

题解

最上面第一题我们写过先序遍历是什么，那么该题我们可以通过先写出先序遍历，然后将左子树赋值为null，右边为下一个节点即可

代码

import java.util.*;class Solution {public static void main(String[] args) {}static List<TreeNode> arr;public void flatten(TreeNode root) {TreeNode ans;arr=new ArrayList<>();if(root==null){return;}dfs(root);ans =new TreeNode(arr.get(0).val);TreeNode now=root;for(int i=1;i<arr.size();i++){now.left=null;now.right=new TreeNode(arr.get(i).val);now=now.right;}}public static void dfs(TreeNode root){if(root==null){return;}arr.add(root);dfs(root.left);dfs(root.right);}}

105. 从前序与中序遍历序列构造二叉树

题意

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点

题解

该题还是比较复杂的，首先我们的先序遍历的第一个节点肯定是根节点，那么我们就可以根据当前的根节点在中序遍历中找到当前的根节点，我们知道中序遍历是左根右，那么根节点之前的就全是左边的字数了，同理右边的就是右子树了，然后我们继续划分即可

代码

import java.util.*;class Solution {public static void main(String[] args) {}public TreeNode buildTree(int[] preorder, int[] inorder) {return build(preorder, 0,preorder.length,inorder,0,inorder.length);}static TreeNode build(int []p,int pl,int pr,int []in ,int ip,int ir){if(pl==pr){return null;}TreeNode root=new TreeNode();root.val=p[pl];int index=0;for(int i=ip;i<=ir;i++){if(in[i]==root.val){index=i;break;}}int sum=index-ip;root.left=build(p,pl+1,pl+sum+1,in,ip,index);root.right=build(p,pl+sum+1,pr,in,index+1,ir);return root;}}

437. 路径总和 III

题意

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

题解

比较简单的做法，我每一次都处理出所有的结果，然后遍历即可，看一下代码就可以理解了

代码

import java.util.*;class Solution {public static void main(String[] args) {}static int ans;public int pathSum(TreeNode root, int targetSum) {ans=0;List<Long> list = dfs(root,targetSum);list.forEach( n -> {if(n==targetSum){ans++;}});return ans;}public static List<Long> dfs(TreeNode root,int sum){if(root==null){return List.of();}List<Long>arr=dfs(root.left,sum);List<Long>brr=dfs(root.right,sum);List<Long> crr=new ArrayList<>();arr.forEach(n -> {if(n==sum){ans++;}crr.add(n+root.val);});brr.forEach(n -> {if(n==sum){ans++;}crr.add(n+root.val);});crr.add((long)root.val);return crr;}}

236. 二叉树的最近公共祖先

题意

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

题解

因为只需要求pq的祖先，我们两种做法，第一找到pq的所有祖先，然后看看有没有相同的，另外一种，也就是下面的代码，就是我们看看左子树和右子树是否同时包含pq即可

代码

import java.util.*;class Solution {public static void main(String[] args) {}static TreeNode ans;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {ans=null;dfs(root,p,q);return ans;}static  boolean dfs(TreeNode root,TreeNode p,TreeNode q){if(root==null){return false;}boolean l=dfs(root.left,p,q);boolean r=dfs(root.right,p,q);if(((l||r)&&(root.val==p.val||root.val==q.val))||(l&&r)){ans=root;}return l||r||root.val==p.val||root.val==q.val;}}

124. 二叉树中的最大路径和

题意

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

题解

说实话，跟上面那个求直径是一样的，也就是将权值为1改为了当前节点的权值，但是有一点需要注意的是，如果《=0，当前节点肯定是需要舍去的

代码

import java.util.*;class Solution {public static void main(String[] args) {}static int maxx=0;public int maxPathSum(TreeNode root) {if(root==null){return 0;}maxx=root.val;dfs(root);return maxx;}static int  dfs(TreeNode root){if(root==null){return 0;}int l=dfs(root.left);int r=dfs(root.right);int sum=0;if(l>=0){sum=sum+l;}if(r>=0){sum=sum+r;}sum=sum+root.val;maxx=Math.max(maxx,sum);return Math.max(Math.max(l,r),0)+root.val;}}