二叉树中两个结点的距离
博客专区 > liujiest 的博客 > 博客详情
二叉树中两个结点的距离
liujiest 发表于2年前
二叉树中两个结点的距离
  • 发表于 2年前
  • 阅读 10
  • 收藏 0
  • 点赞 2
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

原理:两个结点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));
    }
}


  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 6
博文 64
码字总数 26587
×
liujiest
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: