当前位置：网站首页>二叉树相关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);
}
边栏推荐
- The memory of a Zhang
- Single merchant v4.4 has the same original intention and strength!
- 清晰还原31年前现场，火山引擎超清修复Beyond经典演唱会
- 《21天精通TypeScript-3》-安装搭建TypeScript开发环境.md
- RLock锁的使用
- 2020-2022 two-year anniversary of creation
- Explain in detail the functions and underlying implementation logic of the groups sets statement in SQL
- This article takes you through the addition, deletion, modification and query of JS processing tree structure data
- 【深度学习】深度学习如何影响运筹学？
- 用键盘输入一条命令
猜你喜欢
Cs231n notes (medium) -- applicable to 0 Foundation
【网易云信】超分辨率技术在实时音视频领域的研究与实践
清晰还原31年前现场，火山引擎超清修复Beyond经典演唱会
研发效能度量指标构成及效能度量方法论
Batch update in the project
Spring Festival Limited "forget trouble in the year of the ox" gift bag waiting for you to pick it up~
ES6深入—async 函数 与 Symbol 类型
StarkWare：欲构建ZK“宇宙”
obj集合转为实体集合
【深度学习】深度学习如何影响运筹学？
随机推荐
写单元测试的时候犯的错
The database of the server is not connected to 200310060 "unknown error" [the service is up, the firewall is off, the port is on, and the netlent port is not connected]
详解SQL中Groupings Sets 语句的功能和底层实现逻辑
Mongodb getting started Tutorial Part 04 mongodb client
践行自主可控3.0，真正开创中国人自己的开源事业
不敢买的思考
Starkware: to build ZK "universe"
Transaction rollback exception
【深度学习】深度学习如何影响运筹学？
数据湖（十四）：Spark与Iceberg整合查询操作
项目中批量update
【毕业季】作为一名大二计科在校生，我有话想说
清晰还原31年前现场，火山引擎超清修复Beyond经典演唱会
Use of RLOCK lock
The list set is summed up according to a certain attribute of the object, the maximum value, etc
The visual experience has been comprehensively upgraded, and Howell group and Intel Evo 3.0 have jointly accelerated the reform of the PC industry
面对新的挑战，成为更好的自己--进击的技术er
DeSci：去中心化科学是Web3.0的新趋势？
vulnhub-FirstBlood
漫画：什么是服务熔断？