首页 > 数据结构 > 树形结构 > 二叉树中到给定节点距离为K的结点
2014
07-28

二叉树中到给定节点距离为K的结点

问题

给一颗二叉树根节点root和任一个节点target,找出所有到target距离为K的节点。考虑下面的二叉树:

BinaryTree4

例子:假设target 节点为 8,距离K=2,则应该输出节点:10 14 22

这个问题和之前的一个问题 二叉树中两个节点的距离 比较类似。

我们要分情况讨论:

1) 需要查找的节点在target子树下面,比如例子里面的节点 10,14。

2) 需要查找的节点在其他子树里面。比如节点 22

第一种情况可以很容易的使用递归解决。重要是怎么解决第二种情况?

这里可以换一种思路,对于例子中的情况,我们无法直接通过 target (节点8)找到其距离 22 的距离。可以通过 其祖先节点root 节点分别计算左右部分的距离。

假设已经知道当前的 root的左孩子到target的距离为dis_left,则在 root的右孩子下面找出距离右孩子 k – dis_left – 2 距离的节点即可。

例如 target = 4, k = 3. 当前的 root 节点为 20 ,因为 20的左孩子到target的距离为1,而20的左右孩子又相距2,所有早 20的右孩子子树下面查找距离为 3 – 1 -2 =0 的节点,即打印出 22。同理,root节点为8时,可以 找到10,14节点。

详细的java代码如下:

//============================================================================
// Name        : TreeNodesDistanceAtK.java
// Author      : GaoTong
// Date        : 2014/7/26
// Copyright   : www.acmerblog.com
//============================================================================

public class TreeNodesDistanceAtK {
    static class Node{
        Node left,right;
        int data;

        public Node(int i) {
            this.data = i;
        }
    }

    //找到root子树下面的所有距离为k的节点
    public static void kDistanceNodeDown(Node root, int k)
    {
        if (root == null || k < 0)  return;

        if (k==0)
        {
            System.out.println(root.data);
            return;
        }
        kDistanceNodeDown(root.left, k - 1);
        kDistanceNodeDown(root.right, k - 1);
    }

    /**
     * 打印以root为根的二叉树中,到target距离为k的节点
     * @param root 树的根节点
     * @param target 目标节点
     * @param k 距离k
     * @return root到target的距离,-1表示target不在root下面
     */
    public static int kDistanceNode(Node root,Node target ,int k){
        if(root == null) return -1;

        if(root == target){
            kDistanceNodeDown(root, k);
            return 0;
        }

        int dis_left = kDistanceNode(root.left, target, k);
        if(dis_left != -1){
            if(dis_left + 1 == k)
                System.out.println(root.data);
            else
                kDistanceNodeDown(root.right, k-dis_left-2); //左孩子和右孩子之间相差2个距离
            return 1+dis_left;
        }

        //和上面的代码是对称的
        int dis_right = kDistanceNode(root.right, target, k);
        if(dis_right != -1){
            if(dis_right + 1== k)
                System.out.println(root.data);
            else
                kDistanceNodeDown(root.left, k-dis_right-2);
            return dis_right+1;
        }
        return -1;
    }

    public static void main(String args[]){
        Node  root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        root.left.left = new Node(4);
        root.left.right = new Node(12);
        root.left.right.left = new Node(10);
        root.left.right.right = new Node(14);
        Node target = root.left;

        kDistanceNode(root, target, 2);
    }
}

输出:

10
14
22

时间复杂度为 O(N),因为每个节点都最多会被遍历2次。

参考:http://www.geeksforgeeks.org/print-nodes-distance-k-given-node-binary-tree/


  1. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!