当前位置：网站首页>二叉树相关OJ题
二叉树相关OJ题
2022-07-05 15:55:00 【m0_60631323】
目录
1.二叉树的前序遍历
写法一：子问题思路
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret=new ArrayList<>();
if(root==null){
return ret;
}
ret.add(root.val);
List<Integer> left=preorderTraversal(root.left);
ret.addAll(left);
List<Integer> right=preorderTraversal(root.right);
ret.addAll(right);
return ret;
}
写法二：
public void process1(List<Integer> list, TreeNode root){
if(root==null){
return ;
}
list.add(root.val);
process1(list,root.left);
process1(list,root.right);
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list=new LinkedList<>();
process1(list,root);
return list;
}
2.检查两棵子树是否相同
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null&&q==null){
return true;
}
if(p==null||q==null){
return false;
}
if(p.val==q.val){
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
return false;
}
3.另一棵树的子树
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null&&q==null){
return true;
}
if(p==null||q==null){
return false;
}
if(p.val==q.val){
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
return false;
}
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(isSameTree(root,subRoot)) return true;
if(root==null) return false;
if(isSubtree(root.left,subRoot)) return true;
if(isSubtree(root.right,subRoot)) return true;
return false;
}
4.二叉树的最大深度
子问题思路：
二叉树的最大深度等于：左子树的最大深度和右子树的最大深度两者的较大值加1
int getHeight(TreeNode root){
if(root==null){
return 0;
}
int left=getHeight(root.left);
int right=getHeight(root.right);
return left>right?left+1:right+1;
}
5.平衡二叉树
5.1 深度遍历方式
遍历每个节点，看所有节点的左右子树的高度差是否小于等于1
时间复杂度O(n^2) 因为求每个节点的左右子树的高度时都要遍历左右子树的所有节点
int getHeight(TreeNode root){
if(root==null){
return 0;
}
int left=getHeight(root.left);
int right=getHeight(root.right);
return left>right?left+1:right+1;
}
public boolean isBalanced(TreeNode root) {
if(root==null) return true;
int leftH=getHeight(root.left);
int rightH=getHeight(root.right);
return Math.abs(leftH-rightH)<2&&
isBalanced(root.left) &&isBalanced(root.right);
}
5.2 求深度的过程中检查高度差
上面的方法中有重复计算的过程，导致时间复杂度过高
int getHeight(TreeNode root){
if(root==null){
return 0;
}
int left=getHeight(root.left);
int right=getHeight(root.right);
if(left>=0&&right>=0&&Math.abs(left-right)<=1){
return left>right?left+1:right+1;
}else {
return -1;
}
}
public boolean isBalanced(TreeNode root) {
if(root==null) return true;
return getHeight(root)>=0;
}
6.对称二叉树
public boolean isSymmetricChild(TreeNode left,TreeNode right){
if(left==null&&right==null){
return true;
}
if(left==null||right==null){
return false;
}
if(left.val==right.val){
return isSymmetricChild(left.left,right.right)&&isSymmetricChild(left.right,right.left);
}
return false;
}
public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
return isSymmetricChild(root.left,root.right);
}
7.二叉树的构建即遍历
import java.util.*;
class TreeNode{
char val;
TreeNode left;
TreeNode right;
public TreeNode(char val){
this.val=val;
}
}
public class Main {
public static int i=0;
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
while(scan.hasNextLine()){
String str=scan.nextLine();
TreeNode root=create(str);
inOrder(root);
}
}
public static TreeNode create(String str){
TreeNode root=null;
if(str.charAt(i)!='#'){
root=new TreeNode(str.charAt(i));
i++;
root.left=create(str);
root.right=create(str);
}else {
i++;
}
return root;
}
public static void inOrder(TreeNode root){
if(root==null){
return;
}
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}
}
8.最近公共祖先
8.1启发
如果给定的树是一棵二叉搜索树，如何找到最近公共祖先？
8.2 方法一：递归
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null){
return null;
}
if(p==root||q==root){
return root;
}
TreeNode leftR=lowestCommonAncestor(root.left,p,q);
TreeNode rightR=lowestCommonAncestor(root.right,p,q);
if(leftR!=null&&rightR!=null){
//因为在递归的过程中只要遇到p||q==root，就返回，如果leftR和rightR都不为null，说明p，q一定位于根节点的两棵子树上
return root;
}else if(leftR!=null){
//p,q都位于root的左树上
return leftR;
}else if(rightR!=null){
//p,q都位于root的右树上
return rightR;
}
return null;//p,q 不在以root为根的树上（递归过程中root是会变的）
}
8.3方法二：利用栈
在这种方法中，最重要的一步就是如何将从根节点到p
,q的路径上的所有节点存储在栈中
public boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> s){
if(root==null||node==null)return false;
s.push(root);
if(root==node) return true;
boolean flag1=getPath(root.left,node,s);
if(flag1==true){
return true;
}
boolean flag2=getPath(root.right,node,s);
if(flag2==true){
return true;
}
s.pop();
return false;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Stack<TreeNode> s1=new Stack<>();
Stack<TreeNode> s2=new Stack<>();
getPath(root,p,s1);
getPath(root,q,s2);
int size1=s1.size();
int size2=s2.size();
if(size1>size2){
int size=size1-size2;
while(size!=0){
s1.pop();
size--;
}
}else {
int size=size2-size1;
while(size!=0){
s2.pop();
size--;
}
}
while(!s1.empty()&&!s2.empty()){
if(s1.peek()==s2.peek()){
return s1.peek();
}else {
s1.pop();
s2.pop();
}
}
return null;
}
9.根据前序和中序遍历构建二叉树
OJ链接
源码：
int preIndex=0;
private int findInorderRootIndex(int[] inorder,int inbegin,int inend,int val){
for(int i=inbegin;i<=inend;i++){
if(inorder[i]==val){
return i;
}
}
return -1;
}
public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){
if(inbegin>inend){
return null; //此时没有左树或右树
}
TreeNode root=new TreeNode(preorder[preIndex]);
int ri=findInorderRootIndex(inorder,inbegin,inend,preorder[preIndex]);
preIndex++;
root.left=buildTreeChild(preorder,inorder,inbegin,ri-1);
root.right=buildTreeChild(preorder,inorder,ri+1,inend);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChild(preorder,inorder,0,inorder.length-1);
}
注意：
preIndex要定义成全局变量，因为preIndex的值是一直增大的，如果定义成局部变量在递归回退的过程中，preIndex会减小
优化：使用HashMap将中序遍历中的节点和其对应的下标存储在map中，这样在查找ri下标时就不用在去遍历中序遍历的数组了
int preIndex=0;
HashMap<Integer,Integer> map=new HashMap<>();
public void RootIndex(int[] inorder){
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i],i);
}
}
public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){
if(inbegin>inend){
return null; //此时没有左树或右树
}
TreeNode root=new TreeNode(preorder[preIndex]);
int ri= map.get(preorder[preIndex]);
// int ri=findInorderRootIndex(inorder,inbegin,inend,preorder[preIndex]);
preIndex++;
root.left=buildTreeChild(preorder,inorder,inbegin,ri-1);
root.right=buildTreeChild(preorder,inorder,ri+1,inend);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
RootIndex(inorder);
return buildTreeChild(preorder,inorder,0,inorder.length-1);
}
10.根据中序和后序遍历构建二叉树
OJ链接
由于和上一题及其类似，所以这里只说一下二者的区别
区别：
- 后序遍历的顺序是左右根，所以定义postIndex，从后往前遍历后序遍历的数组
- 先递归创建右树，再递归创建左树
int postIndex=0;
HashMap<Integer,Integer> map=new HashMap<>();
public void RootIndex(int[] inorder){
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i],i);
}
}
public TreeNode buildTreeChild1(int[] inorder,int[] postorder,int inbegin,int inend){
if(inbegin>inend){
return null; //此时没有左树或右树
}
TreeNode root=new TreeNode(postorder[postIndex]);
int ri= map.get(postorder[postIndex]);
// int ri=findInorderRootIndex(inorder,inbegin,inend,preorder[preIndex]);
postIndex--;
root.right=buildTreeChild1(inorder,postorder,ri+1,inend);
root.left=buildTreeChild1(inorder,postorder,inbegin,ri-1);
return root;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
RootIndex(inorder);
postIndex=postorder.length-1;
return buildTreeChild1(inorder,postorder,0,inorder.length-1);
}
注意：
postIndex要再函数中赋值
11.二叉树创建字符串
源码：
StringBuilder sb = new StringBuilder();
public String tree2str(TreeNode root) {
dfs(root);
return sb.substring(1, sb.length() - 1);
//最外层不用添加（）
}
void dfs(TreeNode root) {
sb.append("(");
sb.append(root.val);
if (root.left != null) dfs(root.left);
else if (root.right != null) sb.append("()");
if (root.right != null) dfs(root.right);
sb.append(")");
}
12. 二叉树前序非递归遍历实现
源码:
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<>();
if(root==null) return list;
Stack<TreeNode> stack=new Stack<>();
TreeNode cur=root;
while (cur!=null||!stack.empty()){
while (cur!=null){
stack.push(cur);
list.add(cur.val);
cur=cur.left;
}
TreeNode top=stack.pop();
cur=top.right;
}
return list;
}
13.二叉树中序非递归遍历实现
和上一题在大体上类似：
只需调整一下打印元素语句的位置即可
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<>();
Stack<TreeNode> stack=new Stack<>();
TreeNode cur=root;
while (cur!=null||!stack.empty()){
while (cur!=null){
stack.push(cur);
cur=cur.left;
}
TreeNode top=stack.pop();
list.add(top.val);
cur=top.right;
}
return list;
}
14.二叉树后序非递归遍历实现
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) return list;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode prev=null;
while (cur != null || !stack.empty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.peek();
if (top.right == null||top.right==prev) {
list.add(top.val);
stack.pop();
prev=top;
} else {
cur = top.right;
}
}
return list;
}
15.二叉搜索树转双向链表
OJ链接
代码执行的过程分解图：
Node pre=null;
Node head=null;
public Node treeToDoublyList(Node pRootOfTree) {
if(pRootOfTree==null){
return null;
}
inOrder(pRootOfTree);
head.left=pre;
pre.right=head;
return head;
}
private void inOrder(Node cur){
if(cur==null){
return;
}
inOrder(cur.left);
cur.left=pre;
if(pre!=null){
pre.right=cur;
}else {
head=cur;
}
pre=cur;
inOrder(cur.right);
}
边栏推荐
- Use of RLOCK lock
- Relationship between objects and classes
- How can programmers improve their situation?
- 怎样在电脑上设置路由器的WiFi密码
- The list set is summed up according to a certain attribute of the object, the maximum value, etc
- Flet教程之 12 Stack 重叠组建图文混合 基础入门（教程含源码）
- Explain in detail the functions and underlying implementation logic of the groups sets statement in SQL
- 降本40%！Redis多租户集群的容器化实践
- 研发效能度量指标构成及效能度量方法论
- Cartoon: what is service fusing?
猜你喜欢
后台系统发送验证码功能
Starkware: to build ZK "universe"
2020-2022 two-year anniversary of creation
Oneforall installation and use
Data Lake (XIV): spark and iceberg integrated query operation
降本40%！Redis多租户集群的容器化实践
ES6深入—ES6 Generator 函数
视觉体验全面升级，豪威集团与英特尔Evo 3.0共同加速PC产业变革
Research and practice of super-resolution technology in the field of real-time audio and video
DeSci：去中心化科学是Web3.0的新趋势？
随机推荐
Some cognitive thinking
Seaborn绘制11个柱状图
RLock锁的使用
obj集合转为实体集合
Single merchant v4.4 has the same original intention and strength!
The list set is summed up according to a certain attribute of the object, the maximum value, etc
Exception com alibaba. fastjson. JSONException: not match : - =
阿掌的怀念
list使用Stream流进行根据元素某属性数量相加
tf.sequence_mask函数讲解案例
迁移/home分区
视觉体验全面升级，豪威集团与英特尔Evo 3.0共同加速PC产业变革
数据访问 - EntityFramework集成
This article takes you through the addition, deletion, modification and query of JS processing tree structure data
Oneforall installation and use
英特尔第13代Raptor Lake处理器信息曝光：更多核心 更大缓存
Query the latest record in SQL
【网易云信】超分辨率技术在实时音视频领域的研究与实践
Research and development efficiency measurement index composition and efficiency measurement methodology
事务回滚异常