文档章节

二叉树中两个结点的距离

liujiest
 liujiest
发布于 2016/05/07 16:17
字数 357
阅读 13
收藏 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
博文 75
码字总数 34353
作品 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

没有更多内容

加载失败,请刷新页面

加载更多

layer

Layui Layer在open弹出层中异步加载数据和form表单radio、checkbox、select不渲染,不可点击的解决办法 layer 实现弹窗提交信息 function confirmUpdateAward(i) { layer.open({ ...

mickelfeng
55分钟前
0
0
Spring boot中如何获取profiles环境

  实现ApplicationContextAware @Componentpublic class QiNiuPropertiesConfig implements ApplicationContextAware { /// 获取当前环境public String getActiveProfile() { ret......

writeademo
今天
2
0
机器学习中的End-to-End到底是怎么回事?

简单讲就是,Input--->系统(这里指神经网络)--->Output(直接给出输入,NN神经网络就给出结果,一气喝成!!!) 借用一段对话:(http://dy.163.com/v2/article/detail/C3J6F2NJ0511AQHO....

火力全開
今天
2
0
maven多个模块只编译并且只打包指定的模块

在多module的maven项目中,如果每次打包整个工程显得有些冗余和笨重。 命令:mvn clean package install -pl 模块的名称 -am

lifes77
今天
0
0
eosjs中文手册【2.0】

访问地址:eosjs 2.0 中文手册 - 汇智网

汇智网教程
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部