左孩子右兄弟,一道树形DP算法题
本文最后更新于 603 天前,其中的信息可能已经有所发展或是发生改变。

 

分析这个案例,大概可以得出在多叉树在变成二叉树时,无论变成怎么样的一个二叉树,只要这棵树最后一个节点的子节点个数最多的时候,整个二叉树高度最高,此时涉及到树的遍历,即树的DP,啊~好麻烦,思路大概是

我们用map来模拟邻接表操作存储树,表示树的子节点以及其孩子,其中key表示的是父节点,value表示为key的孩子
,存储完树之后,开始寻找树的根节点的子节点最长的那条。于是有以下代码

故由此

import java.util.*;

public class Main {
    //分析这个案例,大概可以得出在多叉树在变成二叉树时,最后一个节点的子节点个数
//最多的时候,整个二叉树高度最高,即height = size+max;
    static Map<Integer, List> map = new HashMap<Integer,List>();
    public Main(int father, int current){
        //我们用map来模拟邻接表操作存储树,表示树的子节点以及
//其孩子,其中key表示的是父节点,value表示为key的孩子
        if (map.containsKey(father)){
//如果对邻接表标示树有疑问,需要补充数据结构的相关知识
            map.get(father).add(current);
        }else{
            map.put(father,new ArrayList());
            map.get(father).add(current);
        }

    }
    public static int dfs(int i, Map<Integer,List> map){
//        这里我们用了树的遍历方式,即树形DP
        if (!(map.containsKey(i))) return 0;
        //当前节点的子树数量
        int size = map.get(i).size();
        //子树的子树的数量的最大值
        int max = 0;
//我们递归先访问到最底层的节点,再一步步的向上递归,
//递归的过程总是难以理解,可以使用流程图去帮助理解
        for (int j = 0;j<size;j++){
            max = Math.max(dfs(map.get(i).get(j),map),max);
        }
        return size+max;

    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        map.put(1,new ArrayList());
        int N = sc.nextInt();
        for (int i = 2;i<N+1;i++){
            new Main(sc.nextInt(),i);
        }
        System.out.println( dfs(1,map));
    }



}

 

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇