文档章节

二叉树中两个结点的距离

一杯82年的JAVA
 一杯82年的JAVA
发布于 2016/05/07 16:17
字数 357
阅读 163
收藏 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));
    }
}


一杯82年的JAVA
粉丝 8
博文 75
码字总数 36425
作品 0
杭州
程序员
私信 提问
加载中
请先登录后再评论。
数据结构之二叉树

1.二叉树的基本概念   二叉树是一种非常常见并实用的数据结构,它结合了有序数组和链表的优点,在二叉树中查找数据与在数组中查找数据一样快,在二叉树中添加删除数据的速度与在链表中一样...

osc_bj19pt0o
2018/05/06
2
0
二叉树中常见的面试题

1 用一个函数判断一棵树是否平衡 题目:实现一个函数检查一棵树是否平衡。对于这个问题而言, 平衡指的是这棵树任意两个叶子结点到根结点的距离之差不大于1。 注意,对于这道题,要审清题意。...

osc_q4og6y57
2018/02/23
1
0
(转) 二叉树常见面试题2

本文整理自:https://www.cnblogs.com/33debug/p/7252371.html 一、常见题型 1. 求两个节点的最近公共祖先; 2. 求二叉树中最远的两个节点的距离; 3. 由前序遍历和中序遍历重建二叉树(如:...

osc_f49nm0tf
2018/09/10
2
0
机器学习算法之kd树

上篇文章讲了 ,但是引出了一个问题: 实现 时,主要考虑的问题是如何对训练数据进行快速 k 近邻搜索。这在特征空间维数大及训练数据容量大时尤其必要。k 近邻法最简单的实现是线性扫描(穷举...

小闫同学啊
02/17
0
0
哈夫曼树

结点到结点之间到距离有意义即权重,并且从树根结点到任意结点的路径长度与该结点上权值的乘积的和,称为该结点的带权路径长度 在含有n个带权叶子结点的二叉树中,其中带权路径长度WPL最小的...

无极之岚
2019/07/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

CentOS6.9下手动编译并安装Python3.7

CentOS6.9默认安装的python版本为2.6.6,若想安装python3以上版本,只能手工编译安装 下面介绍python3.7.3版本的手动编译并安装的步骤 1、下载Python3.7.3的源码包 https://www.python.org/f...

yuanfan2012
2019/05/09
0
0
用canvas画太极图(一步步详解附带源代码)

canvas绘图 该元素负责在页面中设定一个区域,然后由js动态地在这个区域中绘制图形。这个技术最早是由美国苹果公司推出的,目的是为了取代flash,很快主流浏览器都支持它。 绘制路径 要绘制路...

osc_8adtko4d
12分钟前
7
0
iOS逆向开发(5):微信强制升级的突破

接下来的几篇文章,小程以微信为例,实战地演示一下:如何注入iOS的APP。其中使用到的知识,基本在前面的文章中都有介绍到。 小白:小程,我想用回旧版本的微信! 小程:为什么要用旧版本微信...

广州小程
05/21
6
0
时间格式的处理,前端的时间显示2020-07-13T16:02:00.000+0000

在后端添加@JsonFormat @JsonFormat(shape=JsonFormat.Shape.STRING,pattern="yyyy-MM-dd HH:mm:ss",timezone="GMT+8") 在这里插public class CdEqInfoVO { /** * 设备id */......

osc_ekw8urc6
13分钟前
0
0
CLion 中的 Makefile 项目:现已公开!

CLion 2020.2 EAP2 带来了期待已久的 Makefile 项目支持。尽管它仍在初期阶段,具有各种局限性和已知问题,但足以应付大量项目。 您有 Makefile 项目吗?查看原文获取免费的 EAP 版本并立即尝...

Bennyhuo
前天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部