Java 数据结构进阶二叉树题集下
作者：Pretend.. 发布时间：2022-07-11 19:16:18
1、对称二叉树
【OJ链接】
分为以下几种情况：
二叉树为空，是对称二叉树
二叉树不为空，其左子树或者右子树为空，不是对称二叉树
二叉树不为空，左右子树都为空，是对称二叉树
二叉树不为空，左右子树不为空，左右子节点值不同，不是对称二叉树
二叉树不为空，左右子树不为空，左右子节点值相同，如果左子树的左节点和右子树的右节点、左子树的右节点和右子树的左节点相同，则其为对称二叉树，否则，不是对称二叉树。
【代码如下】
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}
return isSymmetricChild(root.left,root.right);
}
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 false;
}
return
isSymmetricChild(left.left,right.right)&&isSymmetricChild(left.right,right.left);
}
}
2、创建并遍历二叉树
【OJ链接】
【题目描述】
读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
关于这个题，完全从零开始，我们需要定义（1）二叉树的节点，（2）中序遍历的函数，（3）根据先序遍历字符串创建二叉树的函数，（4）主函数。创建节点、中序遍历、主函数不用多说。主要说一下根据先序遍历字符串来创建二叉树的过程：
遍历字符串，#表示空，就分为以下两种情况：如果字符不为空，我们需要创建根节点，然后递归创建其的左右子树；否则，直接跳过即可。
【代码如下】
import java.util.Scanner;
//定义二叉树的节点
class TreeNode{
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val){
this.val=val;
}
}
public class Main {
//根据先序遍历字符串创建二叉树
public static int i=0;
public static TreeNode createTree(String s){
TreeNode root=null;
//字符不为空的情况下，创建根节点
if(s.charAt(i)!='#'){
root=new TreeNode(s.charAt(i));
i++;
//递归创建root的左右子树
root.left=createTree(s);
root.right=createTree(s);
}else{
//字符为空，直接跳过
i++;
}
return root;
}
public static void inorderTree(TreeNode root){
if(root==null){
return;
}
inorderTree(root.left);
System.out.print(root.val+" ");
inorderTree(root.right);
}
//中序遍历二叉树
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextLine()){
String s=in.nextLine();
TreeNode node=createTree(s);
inorderTree(node);
}
}
}
3、二叉树中两节点最近公共祖先
【OJ链接】
二叉树的根节点为root，以及两个节点p、q，如果二叉树为空，则返回null；如果二叉树的根节点等于p或者q，或者p、q在根节点的左右两侧，则其最近公共结点为root；如果p、q系欸但在root节点的同侧，则最小公共结点就是该侧的节点。
【代码如下】
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null){
return null;
}
if(root==q||root==p){
return root;
}
TreeNode left=lowestCommonAncestor(root.left,p,q);
TreeNode right=lowestCommonAncestor(root.right,p,q);
if(left==null){
return right;
}
if(right==null){
return left;
}
return root;
}
}
4、二叉搜索树与双向链表
【OJ链接】
二叉搜索树：任何节点的左子树小于右子树
将二叉搜索树转换为有序的双向链表：
二叉搜索树的中序遍历结果为有序的。所以我们只需要写一个中序遍历，在其中实现其节点左右指向的改变即可。首先我们需要一个前驱节点prev来保存每个节点的左节点，初始为null，因为是双向链表，所以prev还需要指向它的右节点，如果其为空，则不用。
【代码如下】
public class Solution {
public TreeNode prev=null;
//中序遍历二叉树
public void inorderTree(TreeNode root){
if(root==null){
return ;
}
inorderTree(root.left);
//处理二叉树的左右节点
root.left=prev;
if(prev!=null){
prev.right=root;
}
prev=root;
inorderTree(root.right);
}
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null){
return null;
}
inorderTree(pRootOfTree);
while(pRootOfTree.left!=null){
pRootOfTree=pRootOfTree.left;
}
return pRootOfTree;
}
}
5、根据前序和中序遍历结果创建二叉树
【OJ链接】
给出一个二叉树的前序遍历和中序遍历的结果，根据其创建二叉树：
我们知道，前序遍历的第一个元素（prev）一定是根节点（从前往后遍历），所以在中序遍历中找到prev，则左边元素为左子树元素，右边元素为右子树，创建根节点，递归创建左子树和右子树。注意一定要先创建左子树，因为先序遍历的因素，先序遍历数组的下一个元素一定是左子树的根节点。【如果是根据后序遍历和中序遍历创建二叉树，则后序遍历的数组需要从后往前遍历，还有，一定要先递归创建右子树】
【代码如下】
class Solution {
public int prevIndex=0;
//找到preorder的prevIndex下标元素在inorder中的位置
public int findIndex(int[] preorder,int[] inorder,int inbegin,int inend){
for(int i=inbegin;i<=inend;++i){
if(inorder[i]==preorder[prevIndex]){
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[prevIndex]);
int index=findIndex(preorder,inorder,inbegin,inend);
prevIndex++;
root.left=buildTreeChild(preorder,inorder,inbegin,index-1);
root.right=buildTreeChild(preorder,inorder,index+1,inend);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChild(preorder,inorder,0,inorder.length-1);
}
}
6、二叉树创建字符串
【OJ链接】
字符串拼接，可以创建StringBuilder方便拼接，先将根节点拼接入字符串，如果其左子树不为空，拼接左括号，递归左子树，递归完后拼接右括号；左树为空的情况下，如果右树也为空，直接拼接右括号，否则，我们拼接空括号，递归右子树，之后再拼接右括号。
【代码如下】
class Solution {
public void tree2strChild(TreeNode root,StringBuilder str){
if(root==null){
return;
}
str.append(root.val);
if(root.left!=null){
str.append("(");
tree2strChild(root.left,str);
str.append(")");
}else{
if(root.right==null){
return;
}else{
str.append("()");
}
}
if(root.right==null){
return;
}else{
str.append("(");
tree2strChild(root.right,str);
str.append(")");
}
}
public String tree2str(TreeNode root) {
StringBuilder str=new StringBuilder();
tree2strChild(root,str);
return str.toString();
}
}
7、非递归实现二叉树前序遍历
【OJ链接】
可以用栈来实现。定义一个栈，将根节点入栈后，去入栈左节点、左节点的左节点……直到为空，去除栈顶元素，入栈其右节点，知道为空，以此循环即可。(中序遍历和前序遍历思路相同）
【代码如下】
class Solution {
public List<Integer> preorderTraversal(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);
list.add(cur.val);
cur=cur.left;
}
TreeNode node=stack.pop();
cur=node.right;
}
return list;
}
}
8、非递归实现二叉树后序遍历
【OJ链接】
初始化一个空栈。当【根节点不为空】或者【栈不为空】时，从根节点开。每次将当前节点压入栈中，如果当前节点有左子树，就往左子树跑，没有左子树就往右子树跑。若当前节点无左子树也无右子树，从栈中弹出该节点，如果当前节点是上一个节点（即弹出该节点后的栈顶元素）的左节点，尝试访问上个节点的右子树，如果不是，那当前栈的栈顶元素继续弹出。
【代码如下】
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<>();
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;
}
}
来源：https://blog.csdn.net/weixin_54342360/article/details/123686341
0
投稿猜你喜欢
- 在C#的List集合操作中，有时候需要查找到List集合中的最大值，此时可以使用List集合的扩展方法Max方法，Max方法有2种形式，一种
- 这篇文章主要介绍了springboot配置aop切面日志打印过程解析,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习
- 先来看两段代码： Thread t = new Thread(() => { AddIt AddDelegate = new
Kotlin开发Android应用实例详解我们简单的知道了Kotlin这门新语言的优势，也接触了一些常见的语法及其简单的使用，相信你会对它有- 本文介绍了Android中js和原生交互的示例代码，分享给大家，具体如下：加载webview的类public class MainActiv
- 前言：发现用Winform做一个圆角按钮遇到麻烦，主要是锯齿问题，后面想了想办法解决问题了。主要方法是按钮的区域通过Region指定，但按钮
- 本文实例讲述了Android仿百度谷歌搜索自动提示框AutoCompleteTextView简单应用。分享给大家供大家参考，具体如下：现在我
- PS:本文使用jdk1.7解析1.Object类 的equals 方法 /** &
- jdk下载并配置下载jdk下图是自己资源管理器中jdk的安装路径，双击然后next就好，不需要改什么配置手里没有安装包的，下载地址在这里 ：
- 一、简述：cmd中，执行java命令与javac命令的区别：javac：是编译命令，将java源文件编译成.class字节码文件。例如：ja
- 先来看我们以前利用RestTemplate发起远程调用的代码：存在下面的问题：代码可读性差，编程体验不统一参数复杂URL难以维护1. Fei
- Activity类处于android.app包中，继承体系如下：1.java.lang.Object2.android.content.Co
- 我们在Android开发中总能看到程序的log日志内容充满了屏幕
- 哈夫曼(Huffman)编码是一种常用的压缩编码方法，是 Huffman 于 1952 年为压缩文本文件建立的。它的基本原理是频繁使用的数据
- 本篇文章依旧采用小例子来说明，因为我始终觉的，案例驱动是最好的，要不然只看理论的话，看了也不懂，不过建议大家在看完文章之后，在回过头去看看理
- 一、参数管理在编程系统中，为了能写出良好的代码，会根据是各种设计模式、原则、约束等去规范代码，从而提高代码的可读性、复用性、可修改，实际上个
- 前言最近学习java，接触到了回调机制(CallBack)。初识时感觉比较混乱，而且在网上搜索到的相关的讲解，要么一言带过，要么说的比较单纯
- 本文实例为大家分享了Android简单使用PopupWindow的的具体代码，供大家参考，具体内容如下思路1.在res下面创建一个menu文
- 本文实例为大家分享了Android实现闪屏页效果的具体代码，供大家参考，具体内容如下1.效果图2.闪屏页逻辑及布局2.1 activity_
- AudioSource 组件参考属性属性说明Clip音频资源Volume音量大小Mute是否静音Loop是否循环Play on load加载
