当前位置：网站首页>二叉树相关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 set tag in SQL
Starkware: to build ZK "universe"
用键盘输入一条命令
Flet教程之 12 Stack 重叠组建图文混合 基础入门（教程含源码）
Research and development efficiency measurement index composition and efficiency measurement methodology
公司自用的国产API管理神器
2020-2022 two-year anniversary of creation
CISP-PTE之PHP伪协议总结
《21天精通TypeScript-3》-安装搭建TypeScript开发环境.md
单商户 V4.4，初心未变，实力依旧！
随机推荐
StarkWare：欲构建ZK“宇宙”
Win11如何给应用换图标？Win11给应用换图标的方法
漫画：什么是蓝绿部署？
[深度学习][原创]让yolov6-0.1.0支持yolov5的txt读取数据集模式
研发效能度量指标构成及效能度量方法论
给自己打打气
How to use FRP intranet penetration +teamviewer to quickly connect to the intranet host at home when mobile office
What is the difference between EDI license and ICP business license
Apple 已弃用 NavigationView,使用 NavigationStack 和 NavigationSplitView 实现 SwiftUI 导航
10 minutes to help you get ZABBIX monitoring platform alarm pushed to nail group
ES6深入—ES6 Class 类
【毕业季】作为一名大二计科在校生，我有话想说
[deep learning] how does deep learning affect operations research?
详解SQL中Groupings Sets 语句的功能和底层实现逻辑
企业级备份软件Veritas NetBackup(NBU) 8.1.1服务端的安装部署
obj解析为集合
This article takes you through the addition, deletion, modification and query of JS processing tree structure data
How can programmers improve their situation?
漫画：什么是八皇后问题？
Starkware: to build ZK "universe"