当前位置:网站首页>二叉树相关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);
}
边栏推荐
- ES6深入—async 函数 与 Symbol 类型
- Background system sending verification code function
- 国泰君安网上开户安全吗
- Transaction rollback exception
- 单商户 V4.4,初心未变,实力依旧!
- Using graylog alarm function to realize the regular work reminder of nail group robots
- Some cognitive thinking
- Domestic API management artifact used by the company
- 漫画:什么是分布式事务?
- Win11提示无法安全下载软件怎么办?Win11无法安全下载软件
猜你喜欢
Flet教程之 12 Stack 重叠组建图文混合 基础入门(教程含源码)
Seaborn绘制11个柱状图
Desci: is decentralized science the new trend of Web3.0?
Cs231n notes (top) - applicable to 0 Foundation
ES6深入—ES6 Class 类
单商户 V4.4,初心未变,实力依旧!
數據訪問 - EntityFramework集成
普洛斯数据中心发布DC Brain系统,科技赋能智慧化运营管理
清晰还原31年前现场,火山引擎超清修复Beyond经典演唱会
2020-2022 two-year anniversary of creation
随机推荐
Five common negotiation strategies of consulting companies and how to safeguard their own interests
企业级备份软件Veritas NetBackup(NBU) 8.1.1服务端的安装部署
【学术相关】多位博士毕业去了三四流高校,目前惨不忍睹……
Cs231n notes (medium) -- applicable to 0 Foundation
利用GrayLog告警功能实现钉钉群机器人定时工作提醒
ES6 drill down - Async functions and symbol types
研发效能度量指标构成及效能度量方法论
List de duplication and count the number
ES6深入—ES6 Class 类
Which keywords will conflict with the abstract keyword
Mongodb getting started Tutorial Part 04 mongodb client
Today's sleep quality record 79 points
Mistakes made when writing unit tests
The list set is summed up according to a certain attribute of the object, the maximum value, etc
Win11如何给应用换图标?Win11给应用换图标的方法
list使用Stream流进行根据元素某属性数量相加
中间表是如何被消灭的?
开发中Boolean类型使用遇到的坑
ES6深入—async 函数 与 Symbol 类型
极坐标扇图使用场景与功能详解