文档章节

求树的直径

datacube
 datacube
发布于 2016/06/22 19:09
字数 349
阅读 14
收藏 0
package com.lifeibigdata.algorithms.blog;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by lifei on 16/6/22.
 */
public class MaxLenInBinTree {

    /*
     a.         1
               /  \
              2    3
             / \  / \
            4   5 6  7
        max=4   pass "root"

     b.         1
               /  \
              2    3
             / \
            4   5
           /     \
          6       7
         /         \
        8           9
        max=6. do not pass "root"
     */

    private int maxLen=0;

    public static void main(String[] args) {
        int[] a={1,2,3,4,5,6,7};  //层级遍历
        //store in LevelOrder,Complete Binary Tree. 0==no child
        MaxLenInBinTree m=new MaxLenInBinTree();

        Node aRoot=m.createTree(a);
        m.findMaxLen(aRoot);
        System.out.println(m.maxLen);

        int[] b={1,2,3,4,5,0,0,6,0,0,7,0,0,0,0,8,0,0,0,0,0,0,9};
        Node bRoot=m.createTree(b);
        m.findMaxLen(bRoot);
        System.out.println(m.maxLen);

    }

    public void findMaxLen(Node node){

        if(node==null) return ;

        if(node.getLeft()==null){
            node.setMaxLeftLen(0);
        }
        if(node.getRight()==null){
            node.setMaxRightLen(0);
        }

        if(node.getLeft()!=null){
            findMaxLen(node.getLeft());
        }
        if(node.getRight()!=null){
            findMaxLen(node.getRight());
        }

        if(node.getLeft()!=null){
            int temp=0;
            Node left=node.getLeft();
            if(left.getMaxLeftLen()>left.getMaxRightLen()){
                temp=left.getMaxLeftLen();
            }else{
                temp=left.getMaxRightLen();
            }
            node.setMaxLeftLen(temp+1);
        }
        if(node.getRight()!=null){
            int temp=0;
            Node right=node.getRight();
            if(right.getMaxLeftLen()>right.getMaxRightLen()){
                temp=right.getMaxLeftLen();
            }else{
                temp=right.getMaxRightLen();
            }
            node.setMaxRightLen(temp+1);
        }
        if(maxLen<node.getMaxLeftLen()+node.getMaxRightLen()){
            maxLen=node.getMaxLeftLen()+node.getMaxRightLen();
        }
    }

    public Node createTree(int[] data){
        List<Node> nodeList=new ArrayList<Node>();
        for(int each:data){
            Node n=new Node(each);
            nodeList.add(n);
        }
        int lastRootIndex=data.length/2-1;
        for(int i=0;i<=lastRootIndex;i++){
            Node root=nodeList.get(i);
            Node left=nodeList.get(i*2+1);
            if(left.getData()!=0){
                root.setLeft(left);
            }else{
                root.setLeft(null);
            }
            if(i*2+2<data.length){
                Node right=nodeList.get(i*2+2);
                if(right.getData()!=0){
                    root.setRight(right);
                }else{
                    root.setRight(null);
                }
            }

        }
        Node root=nodeList.get(0);
        return root;
    }
    class Node{
        private int data;
        private Node left;
        private Node right;
        private int maxLeftLen;//the max length of leftTree
        private int maxRightLen;

        public Node(int i){
            data=i;
        }
        public int getData() {
            return data;
        }
        public void setData(int data) {
            this.data = data;
            this.left=null;
            this.right=null;
        }
        public Node getLeft() {
            return left;
        }
        public void setLeft(Node left) {
            this.left = left;
        }
        public Node getRight() {
            return right;
        }
        public void setRight(Node right) {
            this.right = right;
        }
        public int getMaxLeftLen() {
            return maxLeftLen;
        }
        public void setMaxLeftLen(int maxLeftLen) {
            this.maxLeftLen = maxLeftLen;
        }
        public int getMaxRightLen() {
            return maxRightLen;
        }
        public void setMaxRightLen(int maxRightLen) {
            this.maxRightLen = maxRightLen;
        }
    }
}

本文转载自:

datacube
粉丝 9
博文 607
码字总数 152394
作品 0
海淀
程序员
私信 提问
[BZOJ1791][IOI2008]岛屿Island(基环树的直径)

版权声明:本文为博主原创文章,转载请附上原博客链接。 https://blog.csdn.net/CABI_ZGX/article/details/83477040 传送门     先转换一下题目所给的图:     给一个n个点n条边的图...

_Mocha_
2018/10/28
0
0
树上方法总结 LCA 树上倍增 树链剖分 树的直径 重心

树是一种非常有条理的数据结构,从很多方面来看都是这样。每一个节点有其唯一确定的父亲节点,也有唯一确定的边权或点权。因为没有环,树上可以方便地dfs。并且很多链上的做法都可以推广到树...

myjs999
2017/11/06
0
0
LeetCode算法题-Diameter of Binary Tree(Java实现)

这是悦乐书的第257次更新,第270篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第124题(顺位题号是543)。给定二叉树,您需要计算树的直径长度。 二叉树的直径是树中任意两个...

小川94
02/23
0
0
[APIO2010] 算法竞赛竞赛经典 巡逻

原题链接 题目描述 在一个地区有 n 个村庄,编号为1,2,…,n。 有 n-1 条道路连接着这些村庄,每条道路刚好连接两个村庄,从任何一个村庄,都可以通过这些道路到达其他任一个村庄。 每条道路的...

秦淮岸灯火阑珊
07/12
0
0
LOJ#2339. 「WC2018」通道(边分治+虚树)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/qq_35649707/article/details/82958902 传送门 题解: 考虑两棵树怎么做,要求 相当于对于第一棵树求在第二棵...

DZYO
2018/10/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

HashMap源码分析

read

V丶zxw
43分钟前
5
0
Python字符串或JSON字符串转字典dict、列表list

有3种方法 1、使用ast模块 >>> import ast>>> s = '["test",1]'>>> ast.literal_eval(s)['test',1]>>> s = '{"test":1}'>>> ast.literal_eval(s){'test': 1} 2、eval函数,这个......

编程老陆
今天
5
0
【JS复习笔记】03 继承(从ES5到ES6)

本文转载于:专业的前端网站➫【JS复习笔记】03 继承(从ES5到ES6) 前言 很久以前学习《Javascript语言精粹》时,写过一个关于js的系列学习笔记。 最近又跟别人讲什么原型和继承什么的,发现...

前端老手
今天
8
0
简单动态网站搭建

如何在windows服务器上配置wordPress和discuz 网站建设中的概念讲解 网站建设的基础操作 网站程序的基础使用 网站程序的优化 简单动态网站搭建 软件部署 域名和主机的购买 域名解析 环境部署...

达达前端小酒馆
今天
6
0
Java每日面试题_03

15、构造器是否可被override constructor(构造器)不能被继承,所以不能被override(重写),但是可以被overloading(重载)。 16、抽象类和接口的区别 抽象类是什么 含有abstract修饰符的class即...

庭前云落
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部