JAVA数据结构刷题 -- 二叉树进阶

简介: JAVA数据结构刷题 -- 二叉树进阶

一、二叉树前序递归遍历


根据方法的返回类型List

遍历完二叉树后,返回一个整形的集合

前序遍历,表示按二叉树的根左右进行遍历



参考如下代码(附注解):

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();//创建一个集合用来存储二叉树的信息
        preorder(root,ret);//将二叉树的根和集合作为参数
        return ret;
    }
    public List<Integer> preorder(TreeNode root,List<Integer> list) {
      //若根为空,表示此二叉树是一个空树,直接返回空即可
        if(root == null) {
            return null;
        }
        //若二叉树不为空
        //1.将根节点加到集合当中
        list.add(root.val);
        //2.将根的左子树作为根进行遍历
        preorder(root.left,list);
        //2.将根的右子树作为根进行遍历
        preorder(root.right,list);
        //返回最后的集合
        return list;
    }
}

二、二叉树前序非递归遍历

前序非递归遍历需要用到一个数据结构,首先,当二叉树为空树时,直接返回。

二叉树非空时,借助栈的结构,先判断当前结点是否为空,或者栈是否为空,当满足任意一个条件时,再在当前节点不为空的循环条件下,向栈内添加结点,并打印出来,接着将当前节点的左子树作为根重复进行循环打印,直到当前结点为空时,记录栈顶元素的值并将栈顶元素的右子树作为当前节点进行打印。

如下图示:



参考代码如下:

/**
     * 前序非递归遍历
     * 通过栈存储每一个二叉树结点
     * @param root
     */
    public void preOderNor(TreeNode root) {
        if(root == null) {
            return;
        }
        //创建栈
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        //判断当前结点或栈是否为空
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);//入栈
                System.out.println(cur.val);//打印
                cur = cur.left;//当前节点的左子节点作为下一个结点
            }
            TreeNode top = stack.pop();//弹出并记录栈顶结点
            cur = top.right;//将该栈顶节点的右子节点作为当前节点进行入栈打印操作
        }
    }

三、中序后序还原二叉树

给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

class Solution {
    public int postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length - 1;
        return buildTreeChild(postorder,inorder,0,inorder.length-1);
    }
    private TreeNode buildTreeChild(int[] postorder, int[] inorder,int inbegin,int inend) {
        if(inbegin > inend) {
            return null;
        }
        //确定根节点
        TreeNode root = new TreeNode(postorder[postIndex]);
        //确定根节点值在中序遍历中的位置(下标)
        int rootIndex = findIndex(inorder,inbegin,inend,root.val);
        postIndex--;
        //遍历,先遍历根的右子节点,再遍历根的左子节点
        root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);
        root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);       
        return root;
    }
    //找到根节点在中序遍历数组中的位置,返回所在下标
    private int findIndex(int[] inorder,int inbegin,int inend,int key) {
        for(int i = inbegin;i <= inend; i++) {
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }
}

四、前序中序还原二叉树

给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。

class Solution {
    public int preIndex = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    private TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend) {
        if(inbegin > inend) {
            return null;
        }
        //确定根节点
        TreeNode root = new TreeNode(preorder[preIndex]);
        //确定根节点值在中序遍历中的位置(下标)
        int rootIndex = findIndex(inorder,inbegin,inend,root.val);
        preIndex++;
        //遍历,先遍历根的左子节点,再遍历根的右子节点
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
        return root;
    }
     //找到根节点在中序遍历数组中的位置,返回所在下标
    private int findIndex(int[] inorder,int inbegin,int inend,int key) {
        for(int i = inbegin;i <= inend; i++) {
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }
}

五、两个节点的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(p == root || q == root) return root;
        TreeNode leftRet = lowestCommonAncestor(root.left,p,q);
        TreeNode rightRet = lowestCommonAncestor(root.right,p,q);
        if(leftRet != null && rightRet != null) {
            return root;
        }else if(leftRet != null){
            return leftRet;
        }else {
            return rightRet;
        }
    }
}

六、二叉树的层序遍历

给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

这道题目用到了队列,因为返回值时集合,需要创建一个集合,当二叉树为空时,返回一个空的集合,二叉树不为空,将当前的根节点加入到队列中,当队列不为空时,弹出队头结点并记录他的值,判断对头的左子节点和右子节点是否存在,若存在就加入到队列中进行循环,直到队列为空,循环结束,每次都在0下标位置向集合中添加结点,最后返回集合。

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while (size != 0) {
                TreeNode top = queue.poll();
                list.add(top.val);
                if (top.left != null) {
                    queue.offer(top.left);
                }
                if (top.right != null) {
                    queue.offer(top.right);
                }
                size--;
            }
            //关键点:通过集合的应用,每次添加都从0下标开始,保证题目的要求:自底向上
            ret.add(0,list);
        }
        return ret;
    }
}

七、根据二叉树创建字符串

给你二叉树的根节点 root ,请你采用前序遍历的方式,将二叉树转化为一个由括号和整数组成的字符串,返回构造出的字符串。

空节点使用一对空括号对 “()” 表示,转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

class Solution {
    public String tree2str(TreeNode root) {
        if(root == null) return null;
        StringBuilder stringBuilder = new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
    }
    private void tree2strChild(TreeNode root ,StringBuilder stringBuilder) {
        if(root == null) return;
        stringBuilder.append(root.val);
        if(root.left != null) {
            stringBuilder.append("(");
            tree2strChild(root.left,stringBuilder);
            stringBuilder.append(")");
        }else {
            if(root.right == null) {
                return;
            }else {
                stringBuilder.append("()");
            }
        }
        if(root.right != null) {
            stringBuilder.append("(");
            tree2strChild(root.right,stringBuilder);
            stringBuilder.append(")");
        }else {
            return;
        }
    }
}


相关文章
|
2天前
|
存储 Java API
Java数据结构之ArrayList(如果想知道Java中有关ArrayList的知识点,那么只看这一篇就足够了!)
Java数据结构之ArrayList(如果想知道Java中有关ArrayList的知识点,那么只看这一篇就足够了!)
Java数据结构之ArrayList(如果想知道Java中有关ArrayList的知识点,那么只看这一篇就足够了!)
|
1天前
|
缓存 安全 小程序
从基础到进阶:掌握Java中的Servlet和JSP开发
【6月更文挑战第23天】Java Web开发中的Servlet和JSP是关键技术,用于构建动态网站。Servlet是服务器端小程序,处理HTTP请求,生命周期包括初始化、服务和销毁。基础Servlet示例展示了如何响应GET请求并返回HTML。随着复杂性增加,JSP以嵌入式Java代码简化页面创建,最佳实践提倡将业务逻辑(Servlet)与视图(JSP)分离,遵循MVC模式。安全性和性能优化,如输入验证、HTTPS、会话管理和缓存,是成功应用的关键。本文提供了一个全面的学习指南,适合各级开发者提升技能。
|
3天前
|
机器学习/深度学习 Java Serverless
Java开发者的神经网络进阶指南:深入探讨交叉熵损失函数
今天来讲一下损失函数——交叉熵函数,什么是损失函数呢?大体就是真实与预测之间的差异,这个交叉熵(Cross Entropy)是Shannon信息论中一个重要概念,主要用于度量两个概率分布间的差异性信息。在信息论中,交叉熵是表示两个概率分布 p,q 的差异,其中 p 表示真实分布,q 表示预测分布,那么 H(p,q)就称为交叉熵:
|
2天前
|
Java Android开发 Kotlin
Android面试题:App性能优化之Java和Kotlin常见的数据结构
Java数据结构摘要:ArrayList基于数组,适合查找和修改;LinkedList适合插入删除;HashMap1.8后用数组+链表/红黑树,初始化时预估容量可避免扩容。SparseArray优化查找,ArrayMap减少冲突。 Kotlin优化摘要:Kotlin的List用`listOf/mutableListOf`,Map用`mapOf/mutableMapOf`,支持操作符重载和扩展函数。序列提供懒加载,解构用于遍历Map,扩展函数默认参数增强灵活性。
10 0
|
3天前
|
算法 网络协议 Java
我的Java数据结构和算法
我的Java数据结构和算法
8 0
|
3天前
|
Java 程序员 数据处理
【技能升级】JAVA程序员的进阶之路:掌握URL与URLConnection,轻松玩转网络资源!
【6月更文挑战第21天】在Java中,URL是网络资源的位置标识,如`http://www.example.com/resource.txt`,而URLConnection是与这些资源交互的接口。创建URL对象后,通过`openConnection()`获取URLConnection实例以读取或写入资源。读取时,设置请求头,获取输入流并读取数据;写入(POST)时,设置输出流并写入数据。处理网络操作时,别忘了异常处理、使用连接池以优化性能、设置超时以及恰当使用请求头和响应头。这些最佳实践能助你高效、稳定地进行网络编程。
|
3天前
|
Java
Java 从入门到进阶之路(十九)
Java 从入门到进阶之路(十九)
7 0
|
3天前
|
安全 Java 网络安全
Java Socket编程技术详解:从基础到进阶的全方位指南
【6月更文挑战第21天】Java Socket编程是网络通信的关键,涉及`Socket`和`ServerSocket`类。基础教程展示了如何创建简单的客户端-服务端交互,而进阶内容涵盖了非阻塞I/O、多路复用(如使用`Selector`)以提升性能,以及通过SSL/TLS确保安全通信。学习Socket编程不仅是技术实践,也是理解网络原理的过程,强调了持续学习和实践的重要性。
|
28天前
|
存储 Java
Java数据结构:链表
Java数据结构:链表
31 2
|
28天前
|
Java
DAY-1 | Java数据结构之链表:删除无头单链表中等于给定值 val 的所有节点
力扣203题解:使用时间复杂度为O(n)的思路删除链表中所有值为key的元素。引入辅助指针pre,记录cur的前一个节点,遍历链表时,若cur.val!=key,pre和cur同时前进;若cur.val==key,则pre.next=cur.next,cur继续前进,确保pre不急于跟随以处理连续相同值的情况。遍历结束后,处理头节点可能需要删除的特殊情况。
29 0