读书人

树中随意两个节点之间的距离

发布时间: 2012-12-28 10:29:04 作者: rapoo

树中任意两个节点之间的距离
树中任意两个节点之间的距离是指,从一个节点到另一个几点之间的一条路径。
如果路径上边的权值为1,其它权值为0,那么其实就是计算树的权值。
那么怎样该点是不是在这条路径中呢?
其实并不难,只要我们知道左子树和右子树的权值就可以判断了。
如果左子树和右子树的权值都为0,那么该节点肯定不在要查找的路径上。
否则该节点肯定在查找的路径上。如果左右子树权值都不为0,那么当前节点为公共父节点
,查找结束了,但是递归并不能停下来,所以要标示一下。

static boolean finished = false;public static int findPath(Node root, Node first, Node second) {int value = 0;if (root == first || root == second) {// find the nodevalue = 1;} else if (root == null) {return 0;}int leftvalue = findPath(root.left, first, second);int rightvalue = findPath(root.right, first, second);if (leftvalue * rightvalue != 0 || value * leftvalue != 0|| value * rightvalue != 0) {// find the common parent of the first and second nodefinished = true;return leftvalue + rightvalue;} else if (leftvalue != 0 || rightvalue != 0 || value != 0) {return finished ? leftvalue + rightvalue : leftvalue + rightvalue+ 1;}//return 0;}static class Node {String value;Node left;Node right;}

读书人网 >编程

热点推荐