文档章节

二叉树中两个结点的距离

liujiest
 liujiest
发布于 2016/05/07 16:17
字数 357
阅读 11
收藏 0
点赞 2
评论 0

原理:两个结点A,B往上(根结点)走,会有一个交汇的地方(结点C),那么A,B距离为:A的高度+B的度-C的度*2

//============================================================================
// Name        : TreeNodesDistance.java
// Author      : GaoTong
// Date        : 2014/7/26
// Copyright   : www.acmerblog.com
//============================================================================

class Node{
    Node left,right;
    int key;

    public Node(int i) {
        this.key = i;
    }
}

public class TreeNodesDistance {

    //返回node节点在root中的第几层,-1表示没有在root子树下找到
    public static int findLevel(Node root, int node){
        if(root == null) return -1;
        if(root.key == node) return 0;
        //先在左子树查找
        int level = findLevel(root.left, node);
        //左子树没有找到则到右子树查找
        if(level == -1){
           level = findLevel(root.right, node);
        }
        if(level != -1)
            return level+1;
        return -1;
    }

    public static Node findLCA(Node root, int node1,int node2){
        if(root == null) return null;

        //找到两个节点中的一个就返回
        if(root.key == node1 || root.key == node2){
            return root;
        }

        //分别在左右子树查找两个节点
        Node left_lca = findLCA(root.left, node1, node2);
        Node right_lca = findLCA(root.right, node1, node2);

        if(left_lca != null && right_lca != null){
            //此时说明,两个节点肯定是分别在左右子树中,当前节点比为LCA
            return root;
        }
        return left_lca != null ? left_lca : right_lca;
    }

    public static int distanceNodes(Node root, int node1, int node2){
        Node lca = findLCA(root, node1, node2);
        int dis_lca = findLevel(root, lca.key);
        int dis1 = findLevel(root, node1);
        int dis2 = findLevel(root, node2);
        return dis1 + dis2 - 2*dis_lca;
    }

    public static void main(String args[]){
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.right.left.right = new Node(8);

        System.out.println("Dist(8,7) = " + distanceNodes(root, 8,7));
        System.out.println("Dist(8,3) = " + distanceNodes(root, 8,3));
        System.out.println("Dist(8,3) = " + distanceNodes(root, 8,2));
    }
}


© 著作权归作者所有

共有 人打赏支持
liujiest
粉丝 7
博文 66
码字总数 28338
作品 0
杭州
程序员
算法知识梳理(12) - 二叉树算法第二部分

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 算法知识梳理(5) - 数...

泽毛
2017/12/21
0
0
二叉树知识点回忆以及整理

二叉树 在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”,左子树和右子树同时也是二叉树。二叉树的子树有左右之分,并且次序不能任意颠倒。...

静默加载
2017/10/19
0
0
若干数据结构 && 算法面试题【四】(更新ing)

这是我的第三个面试题汇总。 想看之前的内容请移步 http://zhweizhi.blog.51cto.com/10800691/1763237 若干数据结构 && 算法面试题【一】更新完毕 http://zhweizhi.blog.51cto.com/10800691/...

shangluyi
2016/07/08
0
0
面试算法知识梳理(13) - 二叉树算法第三部分

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 插入排序 希尔排序 选择排序 冒泡排序 计数排序 基数排序 归并排序 快速排序 双向扫描的快速排序 堆排序 面试算法知识梳理(2) - 字...

泽毛
2017/12/22
0
0
二叉树的一些算法

求二叉树中距离最远的2个节点的距离 本文中二叉树结构定义为: 定义:空二叉树的高度为-1,只有根节点的二叉树高度为0,根节点在0层,深度为0。 两个节点的距离为两个节点间最短路径的长度。...

泳泳啊泳泳
2017/12/25
0
0
深入学习二叉树(三) 霍夫曼树

1 前言 霍夫曼树是二叉树的一种特殊形式,又称为最优二叉树,其主要作用在于数据压缩和编码长度的优化。 2 重要概念 2.1 路径和路径长度 在一棵树中,从一个结点往下可以达到的孩子或孙子结点...

进击的Hello_World
05/05
0
0
Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛
2017/11/10
0
0
Kd Tree算法原理和开源实现代码

原文地址: Kd Tree算法原理和开源实现代码 | Tech2Vision + http://www.icvpr.com/kd-tree-tutorial-and-code/ 本文介绍一种用于高维空间中的快速最近邻和近似最近邻查找技术——Kd-Tree(K...

初雪之音
2014/04/13
0
1
Kd-Tree算法原理和开源实现代码

一、Kd-tree Kd-Tree,即K-dimensional tree,是一棵二叉树,树中存储的是一些K维数据。在一个K维数据集合上构建一棵Kd-Tree代表了对该K维数据集合构成的K维空间的一个划分,即树中的每个结点...

Endeavour
2015/11/12
0
0
轻松搞定面试中的二叉树题目

求二叉树中的节点个数 2. 求二叉树的深度 3. 前序遍历,中序遍历,后序遍历 4.分层遍历二叉树(按层次从上往下,从左往右) 5. 将二叉查找树变为有序的双向链表 6. 求二叉树第K层的节点个数 ...

亚特兰缇斯
2015/09/10
151
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

大数据基础知识,大数据学习,涉及的知识点

一、什么是大数据 一种规模大到在获取、存储、管理、分析方面大大超出了传统数据库软件工具能力范围的数据集合,具有海量的数据规模、快速的数据流 转、多样的数据类型和价值密度低四大特征。...

董黎明
11分钟前
0
0
Linux CentOS 7上安装极点五笔

话说几天前在新买的惠普笔记本上成功地安装了Linux CentOS 7操作系统、Nvidia Quandro P600驱动程序及X Window,并在VMware下安装Red Hat教学环境,彻底跳出Windows的苦海,但仍然有一件事不...

大别阿郎
24分钟前
0
0
2018年7月20日集群课程

一、集群介绍 集群,简单地说是指一组(若干个)相互独立的计算机,利用高速通信网络组成一个较大的计算机服务系统,每个集群节点(即集群中的每台计算机)都是运行各自服务的独立服务器。 ...

人在艹木中
26分钟前
0
0
spark开发机中调试snappy

目的 在Idea中的点击运行,使spark可以直接读取snappy 自己编译hadoop,以支持snappy的压缩。 自己编译的目的就是要得到支持snappy文件读写的动态链接库。如果可以在网上下载,可以跳过自行编...

benny周
44分钟前
0
0
centos7 安装docker

1,查看系统版本 cat /etc/redhat-release 2,安装gcc yum -y install gccyum -y install gcc-c++ 3,卸载旧版本 yum remove docker \ docker-client \ ......

暗中观察
44分钟前
0
0
rabbitmq学习记录(七)交换机Exchange-topic

实现功能:一条消息发送给多个消费者 交换机模式:topic 相比于direct匹配模式,匹配routingKey时,topic模式下不仅支持完全匹配,还支持两种特殊的匹配方式 #:可以匹配一个或多个字符 *:可...

人觉非常君
44分钟前
0
0
[译]为什么(要使用)GNU Affero GPL?

#为什么(要使用)GNU Affero GPL? 作者信息:Copyright © 2010, 2013, 2014, 2015 Free Software Foundation, Inc. This page is licensed under a Creative Commons Attribution-NoDeriv......

ICE冰焰火灵X
45分钟前
0
0
apollox-lua 示例

这个项目是从openn2o里迁出的项目。 示例地址 apollox-lua.js 是把js翻译成lua的库。支持两种不同的模态, 在编译工程的时候使用 可以用作openresty的代码翻译, 即用js代替lua。在web模式可...

钟元OSS
55分钟前
0
0
Ubuntu系统笔记 Linux系统

Ubuntu 16.04.3 Ubuntu系统,不适用yum, yum软件源都是RPM软件包,不是deb格式软件包,所以你即便是在Ubuntu上面安装了yum,也是完全用不了的。 不推荐 apt好于yum apt install screen...

阿锋zxf
57分钟前
0
0
Java面试中,遇到这类面试题最吃亏!

从你接触 Java开发到现在,你对 Java最直观的印象是什么呢?是它宣传的 “Compile once, run anywhere”,还是目前看已经有些过于形式主义的语法呢?你对于 Java平台到底了解到什么程度?请你...

Java大蜗牛
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部