"背景 假设需要遍历一棵深度为 n 的树形结构,给出各个节点层级,需要按照节点层级给每个节点编号。 真实的需求是:有一颗树形结构,深度优先遍历时,得到各节点的深度分别为:1,2,2,3,1,2,2,3,4,4,4,此时给它们编号为 1,1.1,1.2,1.2.1,2,2.1,2.2,2.2.1,2.2.1.1,2.2.1 .."

给树形结构节点编号的一种思路

背景

主要思路

    public static void main(String[] args) {
        
        // 层级
        int[] levels = {1,2,2,3,1,2,2,3,4,4};
        int depth = 4;
        // 计数器
        int[] counter = new int[depth];
        for(int i = 0; i < levels.length; i++){
            int curLevel = levels[i];
            // 层级加一
            counter[curLevel - 1] += 1;

            // 归零
            if(i > 0){
                for(int j = curLevel; j < counter.length; j++){
                    counter[j] = 0;
                }
            }
            System.out.println(counter[0] + "." + counter[1] + "." + counter[2]+ "." + counter[3]);
        }
    }

主要思路分析

数组 levels 代表要处理的数据,数组 counter 用于计数,counter[0] 代表深度为 1 的计数器,counter[1] 代表深度为 2 的计数器,依次类推。该思路的平均时间复杂度为 O(depth/2 * n),是线性增长的。

改进思路

 public static void main(String[] args) {
        
        // 层级
        int[] levels = {1,2,2,3,1,2,2,3,4,4};
        int depth = 4;
        // 计数器
        int[] counter = new int[depth];
        int lastLevel = 0;
        for(int i = 0; i < levels.length; i++){
            int curLevel = levels[i];
            // 层级加一
            counter[curLevel - 1] += 1;

            // 归零
            if(i > 0 && curLevel < lastLevel){
                for(int j = curLevel; j < counter.length; j++){
                    counter[j] = 0;
                }
            }
            lastLevel = curLevel;
            System.out.println(counter[0] + "." + counter[1] + "." + counter[2]+ "." + counter[3]);
        }
    }

改进思路分析

由于引入了 lastLevel 的概念,就可以据此判断是否必须归零。该思路的平均时间复杂度为 O(depth/2/m * n), 其中 1<m<depth,它根据实际数据的不同而不同。

  • 思路
    4 引用 • 25 回帖
  • 树形
    1 引用
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    2169 引用 • 7426 回帖 • 1019 关注
感谢    关注    收藏    赞同    反对    举报    分享
回帖    
请输入回帖内容...