文档章节

二叉树中两个结点的距离

liujiest
 liujiest
发布于 2016/05/07 16:17
字数 357
阅读 11
收藏 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

没有更多内容

加载失败,请刷新页面

加载更多

TypeScript基础入门之高级类型的字符串字面量类型

转发TypeScript基础入门之高级类型的字符串字面量类型 高级类型 字符串字面量类型 字符串字面量类型允许你指定字符串必须的固定值。 在实际应用中,字符串字面量类型可以与联合类型,类型保护...

durban
16分钟前
2
0
iOS权限授权添加

<!-- 相册 --> <key>NSPhotoLibraryUsageDescription</key> <string>App需要您的同意,才能访问相册</string> <!-- 相册写入 --> <key>NSPhotoLibraryAddUsageDescription</key> <string>App......

RainOrz
20分钟前
1
0
支配树(Dominator Tree)

MAT中的支配树 在使用MAT分析项目的内存泄漏问题时,其中有一个支配树(Dominator)视图。如果我们把Java对象之间的引用关系看做一张有向图(可以存在环)的话,对象的支配树体现了对象之间的...

akane_oimo
21分钟前
1
0
xshell官网下载及安装(免费版本)

百度搜索xshell,点击xshell官网下载链接,如图 然后点击下图的按钮 点击Latest Products,可以下载最新版本,选择要下载的版本,点击下载 选择上面红框里面的,并填写内容,submit之后会有邮...

曾大大胖
26分钟前
2
0
Android 调用系统分享文字、图片、文件,可直达微信、朋友圈、QQ、QQ空间、微博

兼容SDK 18以上的系统,直接调用系统分享功能,分享文本、图片、文件到第三方APP,如:微信、QQ、微博等 因为偷懒,可直达微信、朋友圈、QQ、QQ空间、微博的分享仅写了图片分享的,其他的文本...

她叫我小渝
28分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部