亲宝软件园·资讯

展开

Java 二叉树

Pretend.. 人气:0

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

加载全部内容

相关教程
猜你喜欢
用户评论