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


相关文章
|
3天前
|
缓存 安全 Java
全面解读ConcurrentHashMap:Java中的高效并发数据结构
全面解读ConcurrentHashMap:Java中的高效并发数据结构
8 2
|
3天前
|
存储 算法 程序员
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
12 4
|
3天前
|
存储
数据结构——二叉树
数据结构——二叉树
6 1
|
3天前
|
运维 Java 程序员
新手进阶:用对if-else,让你的Java逻辑判断不再纠结!
【6月更文挑战第14天】本文介绍了如何有效使用Java中的if-else语句。从基础开始,解释了if-else用于根据条件执行不同代码路径的功能。接着,通过实践演示如何避免过度嵌套以提高代码可读性,利用逻辑运算符简化条件判断,以及在异常处理中运用if-else提升程序健壮性。通过这些最佳实践,旨在帮助开发者更好地掌握if-else,使其成为编程工具箱中的利器。
TU^
|
3天前
|
存储 算法
数据结构~~链式二叉树
数据结构~~链式二叉树
TU^
5 0
|
3天前
|
存储 Java
Java 新手进阶:从变量到常量,一步步走向编程巅峰!
【6月更文挑战第14天】Java新手应掌握变量与常量,它们是编程基础。通过示例展示变量(如矩形的长度和宽度)用于存储可变数据,常量(如重力加速度)用于表示固定值。理解不同类型的变量,如字符串、整型和浮点型,并用`final`关键字定义常量。在银行账户管理程序案例中,变量跟踪账户信息,常量表示年利率。熟悉这些概念将提升编程技能。
|
4天前
|
Java
二叉树搜索 - Java版
二叉树搜索 - Java版
3 0
|
6天前
|
存储
数据结构初阶 初识二叉树
数据结构初阶 初识二叉树
7 0
|
11天前
|
算法
数据结构和算法学习记录——小习题-二叉树的遍历&二叉搜索树
数据结构和算法学习记录——小习题-二叉树的遍历&二叉搜索树
13 0
|
11天前
|
算法
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
13 0