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


相关文章
|
22小时前
|
Java 开发者 UED
【实战攻略】Java异常处理进阶:throw关键字,打造坚不可摧的错误防御体系!
【6月更文挑战第19天】在Java中,`throw`关键字用于主动抛出异常,特别是在检测到错误条件如非法参数时。通过`throw`,开发者能控制何时中断程序并提供清晰的错误信息。例如,在验证订单金额时,如果金额小于等于零,可以抛出`IllegalArgumentException`。此外,`throw`还可用于构建异常链,保留错误上下文,便于问题追溯。掌握`throw`使用,是构建健壮异常处理和提升用户体验的关键。
|
1天前
|
存储 Java 数据管理
告别混乱!用Java Map优雅管理你的数据结构
【6月更文挑战第18天】Java Map接口简化了数据管理,如在购物平台开发中。用Map存储商品ID与对象,便于查找、修改和删除。用户管理中,Map以用户ID为键存储用户信息,支持登录验证和信息更新。订单管理同样受益,订单ID与订单对象配对,易于查询和状态变更。Map使得数据结构清晰,提升代码效率。
|
1天前
|
存储 Java 数据处理
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【6月更文挑战第18天】在Java中,HashMap基于哈希表提供快速的键值对操作,适合无序数据;而TreeMap利用红黑树保证排序,适用于有序场景。示例展示了HashMap如何存储并查找用户信息,以及TreeMap如何按员工编号排序存储员工名。两者在不同需求下优化了数据处理。
|
2天前
|
算法 Java 索引
【算法】重建二叉树并进行后序遍历的Java实现
【算法】重建二叉树并进行后序遍历的Java实现
14 5
|
2天前
|
存储 Java 索引
【Java】LinkedList vs. ArrayList:Java中的数据结构选择
【Java】LinkedList vs. ArrayList:Java中的数据结构选择
10 3
|
2天前
|
存储 算法
【二叉树】数据结构——BST二叉树基本概念及算法设计(插入、删除、遍历操作)
【二叉树】数据结构——BST二叉树基本概念及算法设计(插入、删除、遍历操作)
|
2天前
|
存储 算法
【树】数据结构——树和二叉树的概念&笔记
【树】数据结构——树和二叉树的概念&笔记
|
1天前
|
算法
$停车场管理系统 栈与队列
$停车场管理系统 栈与队列
5 1
|
2天前
|
存储 缓存 算法

热门文章

最新文章