• 刷题之完全二叉树的权值和小字辈及根据后序和中序遍历输出先序遍历


    1、完全二叉树的权值

    1)题目

    给定一棵包含 N 个节点的完全二叉树,树上每个节点都有一个权值,按从 上到下、从左到右的顺序依次是 A1, A2, ··· AN,如下图所示:

    现在小明要把相同深度的节点的权值加在一起,他想知道哪个深度的节点 权值之和最大?如果有多个深度的权值和同为最大,请你输出其中最小的深度。

    注:根的深度是 1。

    输入格式:

    第一行包含一个整数 N(1≤N≤10^5)。

    第二行包含 N 个整数 A1, A2, ··· AN (−10^5 <= Ai<=10^5)。

    输出格式:

    输出一个整数代表答案。

    输入样例:

    在这里给出一组输入。例如:

    1. 7
    2. 1 6 5 4 3 2 1

    输出样例:

    在这里给出相应的输出。例如:

    2

     2)题目解析

     题目要求我们输入n个数字,这n个数字是一颗树的层序遍历,并且这是一颗完全二叉树。计算哪一层数字之和最大,并输出该层数。注:根的深度是 1。

     3)代码 

    1. import java.util.Scanner;
    2. public class Main {
    3. public static void main(String[] args) {
    4. Scanner sc=new Scanner(System.in);
    5. int n=sc.nextInt();
    6. long []arr= new long[n];
    7. for (int j=0;j
    8. arr[j]=sc.nextInt();
    9. }
    10. //第一层只有一个节点,p表示该层的节点数
    11. int p=1;
    12. //max表示当前 最大权值之和
    13. long max = 0;
    14. //l表示max所在的层数,l1是跟着循环遍历的层数
    15. int l=1,l1=1;
    16. //i表示节点总数3,不超过n
    17. int i=0;
    18. while (i
    19. int j=p;
    20. //max1表示当前层的权值之和
    21. long max1=0;
    22. //j=p,表示该层的节点数
    23. while (j!=0){
    24. max1+=arr[i++];
    25. j--;
    26. if (i==n)
    27. break;
    28. }
    29. //判断当前层是否是最大权值之和
    30. if (max
    31. max = max1;
    32. l=l1;
    33. }
    34. //下一层的节点数=p*2,深度=l1+1
    35. p*=2;
    36. l1++;
    37. }
    38. System.out.println(l);
    39. }
    40. }

     2、小字辈

    1)题目

    本题给定一个庞大家族的家谱,要请你给出最小一辈的名单。

    输入格式:

    输入在第一行给出家族人口总数 N(不超过 100 000 的正整数) —— 简单起见,我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号,其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。

    输出格式:

    首先输出最小的辈分(老祖宗的辈分为 1,以下逐级递增)。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔,行首尾不得有多余空格。

    输入样例:

    1. 9
    2. 2 6 5 5 -1 5 6 4 7


    输出样例:

    1. 4
    2. 1 9

     2)题目解析

     题目要求我们输入N个数,这N个数表示从1到N的其父节点编号,家谱中辈分最高的老祖宗对应的父/母编号为 -1,然后找出其最小辈的编号。输入样例对应图如下图,可以帮助你们更好理解。

     

     3)代码

    1. import java.util.*;
    2. public class Main1 {
    3. //L表示当前递归到的最大层数
    4. static int L;
    5. //使用队列来存储结果,先进先出
    6. static Queue queue=new LinkedList<>();
    7. //递归函数
    8. static void sonTree(int []arr,int father,int l){
    9. for (int i=1;i
    10. //如果arr[i]=father,表示编号为i的父亲是father,再进入递归函数,
    11. //寻找以i为父亲的子节点
    12. if (arr[i]==father){
    13. sonTree(arr,i,l+1);
    14. }
    15. }
    16. //如果当前递归的l小于L(当前递归到的最大层数),直接return,肯定不是最小辈
    17. if (l
    18. return;
    19. if (l>L){
    20. //如果当前递归的l大于L(当前递归到的最大层数),即是新的最大递归层数,
    21. // 清空队列,重新添加元素
    22. L=l;
    23. queue.clear();
    24. }
    25. queue.add(father);
    26. }
    27. public static void main(String[] args) {
    28. Scanner sc=new Scanner(System.in);
    29. int n=sc.nextInt();
    30. int []arr=new int[n+1];
    31. int x=0; //x表示-1祖宗的编号
    32. for (int i=1;i<=n;i++){
    33. arr[i]=sc.nextInt();
    34. //记录祖宗的编号
    35. if (arr[i]==-1)
    36. x=i;
    37. }
    38. //从1楼开始
    39. int l=1;
    40. sonTree(arr,x,l);
    41. System.out.println(L);
    42. while (queue.size()!=1){
    43. System.out.print(queue.poll()+" ");
    44. }
    45. System.out.print(queue.poll());
    46. }
    47. }

     上述代码是递归方法,但是因为题目数据量过大,N(不超过 100 000 的正整数),因此部分题给用例会超时或者其他错误,欢迎大佬在评论区给出建议。下面是正确的另一种方法:

    1. import java.io.BufferedReader;
    2. import java.io.IOException;
    3. import java.io.InputStreamReader;
    4. import java.util.*;
    5. public class Main {
    6. public static void main(String[] args) throws IOException {
    7. //因为题目数据用量特别大,所以用BufferedReader,提高数据读取时间
    8. BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
    9. int n=Integer.parseInt(bf.readLine());
    10. //因为所给数据是每个人的父母,所以用arr[]来存放第i人的子女
    11. ArrayList arr[]=new ArrayList[n+1];
    12. for (int i=0;i1;i++){
    13. //先要给每个arr[]分配内存,不然都是null
    14. arr[i]=new ArrayList<>();
    15. }
    16. int[] count=new int[n+1];//存放每个人的辈分
    17. Queue q=new LinkedList<>();//层序遍历来求辈分
    18. //如果只有一个人直接输出
    19. if (n==1){
    20. System.out.println(1);
    21. System.out.print(1);
    22. return;
    23. }
    24. //读取n个数据
    25. String s=bf.readLine();
    26. String[] ss=s.split(" ");
    27. int x=0;
    28. int lzz=0;//记录老祖宗的编号
    29. for (int i=1;i<=n;i++){
    30. x= Integer.parseInt(ss[i-1]);
    31. //记录祖宗的编号
    32. if (x==-1)
    33. lzz=i;
    34. else//将i加入到该第x个ArrayList集合中,表示第i个人是第x个人的子女,
    35. arr[x].add(i);
    36. }
    37. //先将老祖宗入队
    38. q.add(lzz);
    39. int L=1;//表示辈分
    40. count[lzz]=1;//老祖宗的辈分是1
    41. while (!q.isEmpty()){
    42. int t=q.peek();
    43. q.poll();
    44. for (int i=0;i
    45. count[arr[t].get(i)]=count[t]+1;//更新每个子女的辈分
    46. //更新新的最小辈分的值
    47. L=Math.max(L,count[arr[t].get(i)]);
    48. //把子女入队
    49. q.add(arr[t].get(i));
    50. }
    51. }
    52. System.out.println(L);
    53. boolean b=true;
    54. //输出
    55. for (int i=1;i<=n;i++){
    56. if (count[i]==L){
    57. if (b){
    58. System.out.println(i);
    59. b=false;
    60. }else
    61. System.out.println(" "+i);
    62. }
    63. }
    64. }
    65. }

     为了更好理解可以看看下面图,先找到5的子女并放入arr[x]中。子女的辈分值为 二,然后在count[]的相应位置存储其辈分值。然后再找3,4,6的子女并放入3,4,6对应的arr[]中,其对应的子女的辈分值为3·· ···

    L为最大的辈分值,即是最小辈分,然后去count[]数组中找与L相等的辈分值,并输出其对应的i值。

     

     3、根据后序和中序遍历输出先序遍历

    1)题目

    本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。

    输入格式:

    第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间以空格分隔。题目保证输入正确对应一棵二叉树。

    输出格式:

    在一行中输出Preorder: 以及该树的先序遍历结果。数字间有1个空格,行末不得有多余空格。

    输入样例:

    1. 7
    2. 2 3 1 5 7 6 4
    3. 1 2 3 4 5 6 7

    输出样例:

    Preorder: 4 1 3 2 6 5 7

     2)题目解析

    题目给定我们N个数,然后在下两行分别给出由这N个数组成的一颗二叉树的后序遍历和中序遍历。然后要求我们输出前序遍历。我们应该先根据后序遍历和中序遍历,构建出这颗二叉树,然后再进行前序遍历并输出。

     3)代码

    1. import java.util.*;
    2. public class Main {
    3. public static class TreeNode {
    4. int val;
    5. TreeNode left;
    6. TreeNode right;
    7. TreeNode(int val) {
    8. this.val = val;
    9. }
    10. }
    11. public static void main(String[] args) {
    12. Scanner sc=new Scanner(System.in);
    13. int n=sc.nextInt();
    14. int []hx=new int[n];
    15. int []qx=new int[n];
    16. for (int i=0;i
    17. hx[i]=sc.nextInt();
    18. }
    19. for (int i=0;i
    20. qx[i]=sc.nextInt();
    21. }
    22. TreeNode tree=buildTree(qx,hx);
    23. //使用List集合存储该树的前序遍历,方便输出
    24. List list=new ArrayList<>();
    25. preorder(tree,list);
    26. int j=0;
    27. System.out.print("Preorder: ");
    28. while (j!=list.size()-1){
    29. System.out.print(list.get(j)+" ");
    30. j++;
    31. }
    32. System.out.print(list.get(j));
    33. }
    34. //前序遍历,使用List 集合存储
    35. public static void preorder(TreeNode root, Listlist){
    36. if (root == null) {
    37. return;
    38. }
    39. list.add(root.val);
    40. preorder(root.left, list);
    41. preorder(root.right, list);
    42. }
    43. //前序遍历
    44. public static void preOrder(TreeNode head) {
    45. if (head == null) {
    46. return;
    47. }
    48. System.out.print(head.val + " ");
    49. preOrder(head.left);
    50. preOrder(head.right);
    51. }
    52. static int index = 0;
    53. //构建二叉树
    54. public static TreeNode buildTree(int[] inorder, int[] postorder) {
    55. index = postorder.length-1;
    56. return buildTree(postorder, inorder, 0, inorder.length);
    57. }
    58. // index不断在后序遍历中找根节点,每次找完之后,根据找到的根节点将中序遍历分成
    59. //左右两部分,左侧为根的左子树,右侧为根的右子树
    60. // 注意:与前序中序还原二叉树不同的是,此次需要先还原右子树
    61. private static TreeNode buildTree(int[] postorder, int[] inorder, int left,
    62. int right){
    63. //如果left>=right,即左右节点遍历到同一节点,这时就要停止递归
    64. if(left >= right){
    65. return null;
    66. }
    67. // 创建根节点
    68. TreeNode root = new TreeNode(postorder[index]);
    69. // 在中序遍历结果中找到根的位置
    70. int rootIdx = left;
    71. //寻找根位置
    72. while(rootIdx < right){
    73. if(inorder[rootIdx] == postorder[index])
    74. break;
    75. rootIdx++;
    76. }
    77. index--;
    78. //要先构建右子树,再构建左子树,这是由后序遍历决定的
    79. //[rootIdx+1, right): 右子树中的所有节点的范围
    80. // 递归创建根的右子树
    81. root.right = buildTree(postorder, inorder, rootIdx+1, right);
    82. //[left, rootIdx):左子树中的所有节点的范围
    83. // 递归创建根的左子树
    84. root.left = buildTree(postorder, inorder, left, rootIdx);
    85. return root;
    86. }
    87. }

    其实根据后序和中序写出前序 和根据前序和中序写出后序是差不多的,只不过是从前往后遍后序,先构建左子树,过程都是差不多的。希望可以用帮助到大家。

     👍👍👍看到这里了还不点个赞👍👍👍

     

  • 相关阅读:
    package.json 依赖版本中的符号含义
    使用svm-svc算法对乳腺癌进行预测
    云原生之深入解析如何使用Vcluster Kubernetes加速开发效率
    哈佛参考文献注释体系与学术规范
    如何批量图片重命名不同名字?
    P1~P2 模板起源
    mycat实现mysql读写分离
    el-select 搜索无选项时 请求接口添加输入的值
    大模型创业“风投”正劲,AGI Foundathon 大模型创业松活动精彩看点
    Debian11安装MySQL8.0,链接Navicat
  • 原文地址:https://blog.csdn.net/m0_63951142/article/details/128098640