Java 数据结构进阶二叉树题集下

Java 数据结构进阶二叉树题集下

目录1、对称二叉树2、创建并遍历二叉树3、二叉树中两节点最近公共祖先4、二叉搜索树与双向链表5、根据前序和中序遍历结果创建二叉树6、二叉树创建字符串7、非递归实现二叉树前序遍历8、非递归实现二叉树后序遍历

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){

ZdQqOi 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 ZdQqOi{

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 preorderTraversal(TreeNode root) {

List list=new ArrayList<>();

Stack 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 postorderTraversal(TreeNode root) {

List list=new ArrayList<>();

Stack 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;

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。