首页 > 数据结构 > 树形结构 > 二叉树中两个结点的距离
2015
10-26

二叉树中两个结点的距离

问题

对于普通的二叉树,如何找到两个给定节点之家的距离?距离是指连接两个节点需要的最小的边的条数。

例如下面的二叉树:

dist

 

这个问题很全面的考察了二叉树相关的知识,建议大家先尝试自己解决~

分析

假设给定的节点为node1, node2,可以分为下面两种情况:

1) node1是node2的祖先节点或孩子节点,可以理解为两个节点在一条线上。 例如:Dist(2,4), Dist(6,1)

2) node1 和 node2 没有直接或间接的父子关系。 例如,Dist(4,3), 他们需要一个共同的祖先节点1 连接起来。

关于两个节点的最低公共祖先(LCA)问题,可以参考:寻找二叉树两个节点的最低公共祖先

通过观察可以总结出下面的公式, lca是两个节点的最低公共祖先节点:

Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2*Dist(root, lca) 

 这个公式已经含盖了上面的两种情况。先找出lca,再求root节点到某个节点的距离就比较简单了。

下面是Java代码实现:

//============================================================================
// 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));
    }
}

时间复杂度为 O(N).

参考:www.geeksforgeeks.org/find-distance-two-given-nodes/


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. This write-up presents the gentle in which we can notice the fact. this is extremely wonderful one and gives in depth info.

  3. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  4. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }

  5. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge