blocks|key|1348754|text|几乎可以肯定的是，找到共同的祖先是更容易的任务。这是一个非常简单的方法:从树的根开始，然后沿着树向下，直到到达一个节点，在这个节点上，您必须下降到不同的子节点才能到达所讨论的两个节点。该节点是公共的父节点(当然，假设树包含这两个节点)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1348755|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Finding the common ancestor is almost certainly the easier task. This is a pretty simple one: start from the root of the tree, and descend the tree until you reach a node where you would have to descend to different children to get to the two nodes in question. That node is the common parent (assuming the tree contains both nodes, of course).

blocks|key|1348873|text|这里的每个人似乎都知道，如果你记下每个节点到根的距离，那么一旦你找到了两个节点的最低公共祖先，你就可以在恒定的时间内计算出它们彼此之间的距离。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1348874|如果你只做一次与树大小成线性的工作，那么你就可以在固定的时间内找到任意两个节点的最低公共祖先(无论树有多深)。请参阅http://en.wikipedia.org/wiki/Lowest_common_ancestor|offset|length|1348875|Baruch+Schieber和Uzi+Vishkin的最低共同祖先算法在使用和编程上是完全实用的。|1348876|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Lowest_common_ancestor^0|0|1M|1F|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@$D|R|E|S|1|T]]|A|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]]]

As everybody here seems to know, if you keep a note of the distance each node is from the root, then once you have found the lowest common ancestor of the two nodes you can work out the distance they are from each other in constant time. 

If you do one time work only linear in the size of the tree it turns out that you can then find the lowest common ancestor of any two nodes in constant time (no matter how deep the tree is). See <a href="http://en.wikipedia.org/wiki/Lowest_common_ancestor" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Lowest_common_ancestor</a>

The Baruch Schieber and Uzi Vishkin algorithm for lowest common ancestor is entirely practical to use and to program.

blocks|key|1348808|text|创建由每个节点的祖先组成的两个集合:当集合的并集为空时，将每个节点的下一个祖先添加到适当的列表中。一旦有了公共节点，那就是公共祖先。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1348809|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Make two sets consisting of the ancestors of each: while the union of the sets is empty, add the next ancestor of each node to the appropriate list. Once there is a common node, that's the common ancestor.

blocks|key|1348941|text|首先，搜索第一个元素的高度。另外，使用链表返回到达该位置的路径。您可以在O(logN)时间内完成此操作。假设树是平衡的，其中高度是logN。让H1+=第一个元素的高度。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1348942|然后，搜索第二个元素的高度。另外，使用链表返回到达该位置的路径。您可以在O(logN)时间内完成此操作。让H2+=第二个元素的高度。|1348943|跟踪收集到的两个链表，直到值不再相等(路径分叉)之前的点，称为该节点的高度H3。|1348944|因此，最长的路径是H1+%2B+H2+-+2*H3+(因为您需要H1转到H1，需要H2转到H2。但实际上，您可以从H1追溯到H1-H3。然后从H3移动到H2。所以它是(H1-H3)+%2B+(H2-H3)+=+H1%2BH2+-2*H3。|1348945|实现细节应该直截了当|1348946|search(Tree*+Head,+Node*+Value,+LinkedList+path,+int+distance);+|code-block|syntax|javascript|1348947|因此，|1348948|search(Head,+Value1,+path1,+height1);+
search(Head,+Value2,+path2,+height2);+

i+=+0;+
while+(path1[i]+==+path2[i])
{
++++i%2B%2B;+
}
height3+=+i-1;+
return+height1%2Bheight2-+2*height3;+|1348949|时间复杂度:+O(logN)%2B+O(logN)+%2B+O(logN)+=+O(logN)空间复杂度:+O(logN)+(存储两个链表的距离)|1348950|entityMap^0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|X|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|Y|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|Z|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|10|8|@]|9|@]|A|$]]|$1|J|3|K|5|L|7|11|8|@]|9|@]|A|$M|N]]|$1|O|3|P|5|6|7|12|8|@]|9|@]|A|$]]|$1|Q|3|R|5|L|7|13|8|@]|9|@]|A|$M|N]]|$1|S|3|T|5|6|7|14|8|@]|9|@]|A|$]]|$1|U|3|-4|5|6|7|15|8|@]|9|@]|A|$]]]|V|$]]

First, 
search for the height of the first element. 
Also, return the path to get there using a linked list. 
You can do this in O(logN) time . Assume tree is balanced, where height is logN.
let H1 = height of first element. 

Then, 
search for the heigh to the second element. 
Also, return the path to get there using a linked list. 
You can do this in O(logN) time. 
Let H2 = height of second element. 

Trace through both linked list collected until the values are no longer equal (paths diverge)
The point before they diverge, call the height of that node H3. 

Thus, the longest path is 
H1 + H2 - 2*H3 (since you need H1 to go to H1, and H2 to go to H2. But really, 
you can trace back from H1 up till H1-H3. and then move to H2 from H3. 
So it's (H1-H3) + (H2-H3) = H1+H2 -2*H3.

Implementation details should be straight forward

<pre><code>search(Tree* Head, Node* Value, LinkedList path, int distance); 
</code></pre>

Thus, 

<pre><code>search(Head, Value1, path1, height1); 
search(Head, Value2, path2, height2); 

i = 0; 
while (path1[i] == path2[i])
{
 i++; 
}
height3 = i-1; 
return height1+height2- 2*height3; 
</code></pre>

Time Complexity: O(logN)+ O(logN) + O(logN) = O(logN)
Space Complexity: O(logN) (to store both linked list of distances)

blocks|key|1348992|text|这是BT距离的DP实现。不是最优的，但很有趣。它首先使用一个输入数组创建树。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1348993|import+java.util.ArrayList;
import+java.util.HashMap;
import+java.util.List;
import+java.util.Map;

/**
+*+Created+by+juanmf+on+05/02/17.
+*/
public+class+Main2+{
++++/**
+++++*+{50,+60,+30,+10,+20,+40}+will+form+a+Node+Structure+as+follows
+++++*+5
+++++*+├─L─+3
+++++*+│  +├─L─+1
+++++*+│  +│  +└─R─+2
+++++*+│  +└─R─+4
+++++*+└─R─+6
+++++*+L:+left
+++++*+R:+Right
+++++*+Path+should+be:+[4,+3,+1,+2]
+++++*+steps:+3+<-+output
+++++*
+++++*+@param+args
+++++*/
++++public+static+void+main(String[]+args)+{
++++++++int+i+=+pathSteps(new+int[]+{50,+60,+30,+10,+20,+40},+6,+20,+60);
++++++++System.out.println(i);
++++}

++++private+static+int+pathSteps(int[]+ints,+int+n,+int+from,+int+to)+{
++++++++Node+root+=+null;
++++++++Map<Node,+Node>+allNodes+=+new+HashMap<>();

++++++++for+(int+i:+ints)+{
++++++++++++if+(root+==+null)+{
++++++++++++++++root+=+new+Node(i);
++++++++++++++++allNodes.put(root,+root);
++++++++++++}
++++++++++++root.addNode(i,+allNodes);
++++++++}
++++++++Map<Node,+List<Node>>+cache+=+new+HashMap<>();

++++++++Node+fromN+=+new+Node(from);
++++++++Node+toN+=+new+Node(to);

++++++++if+(!+allNodes.containsKey(fromN)+%7C%7C+!+allNodes.containsKey(toN))+{
++++++++++++return+-1;
++++++++}
++++++++fromN+=+allNodes.get(fromN);
++++++++toN+=+allNodes.get(toN);

++++++++List<Node>+path+=+traverse(fromN,+toN,+cache);
++++++++return+path.size()+-+1;
++++}

++++private+static+List<Node>+traverse(Node+fromN,+Node+toN,+Map<Node,+List<Node>>+cache)+{

++++++++if(cache.containsKey(fromN))+{
++++++++++++System.out.println("cache+Hit:+"+%2B+fromN);

++++++++++++return+cache.get(fromN);
++++++++}
++++++++System.out.println("visiting:+"+%2B+fromN);
++++++++if+(fromN+==+null+%7C%7C+fromN.visited)+{
++++++++++++return+new+ArrayList<>();
++++++++}
++++++++if+(fromN.equals(toN))+{
++++++++++++List<Node>+target+=+new+ArrayList<>();
++++++++++++target.add(toN);
++++++++++++return+target;
++++++++}
++++++++fromN.visited+=+true;

++++++++List<Node>+parentWay+=+new+ArrayList<>();
++++++++List<Node>+lchildWay+=+new+ArrayList<>();
++++++++List<Node>+rchildWay+=+new+ArrayList<>();

++++++++parentWay.addAll(traverse(fromN.parent,+toN,+cache));
++++++++lchildWay.addAll(traverse(fromN.lchild,+toN,+cache));
++++++++rchildWay.addAll(traverse(fromN.rchild,+toN,+cache));

++++++++List<Node>+shortest+=+getShortestList(getShortestList(parentWay,+lchildWay),+rchildWay);

++++++++cache.put(fromN,+shortest);
++++++++if+(!+shortest.isEmpty())+{
++++++++++++shortest.add(fromN);
++++++++}
++++++++fromN.visited+=+false;
++++++++System.out.println(shortest);
++++++++return+shortest;
++++}

++++private+static+List<Node>+getShortestList(List<Node>+l1,+List<Node>+l2+)+{
++++++++List<Node>+shortest+=+null;
++++++++if+(l1+!=+null+&+l2+!=+null)+{
++++++++++++if+(l1.isEmpty())+{
++++++++++++++++shortest+=+l2;
++++++++++++}+else+if+(l2.isEmpty())+{
++++++++++++++++shortest+=+l1;
++++++++++++}+else+{
++++++++++++++++shortest+=+l1.size()+<+l2.size()+?+l1+:+l2;
++++++++++++}
++++++++}+else+if+(l1+==+null)+{
++++++++++++shortest+=+l2;
++++++++}+else+if+(l2+==+null)+{
++++++++++++shortest+=+l1;
++++++++}
++++++++return+shortest;
++++}

++++private+static+class+Node+{
++++++++Node+parent;
++++++++Node+lchild;
++++++++Node+rchild;

++++++++final+int+value;
++++++++public+boolean+visited;

++++++++private+Node(int+value)+{
++++++++++++this.value+=+value;
++++++++}

++++++++public+void+addNode(int+i,+Map<Node,+Node>+allNodes)+{
++++++++++++if+(i+>+value)+{
++++++++++++++++if+(null+==+rchild)+{
++++++++++++++++++++rchild+=+new+Node(i);
++++++++++++++++++++rchild.parent+=+this;
++++++++++++++++++++allNodes.put(rchild,+rchild);
++++++++++++++++}+else+{
++++++++++++++++++++rchild.addNode(i,+allNodes);
++++++++++++++++}
++++++++++++}
++++++++++++if+(i+<+value)+{
++++++++++++++++if+(null+==+lchild)+{
++++++++++++++++++++lchild+=+new+Node(i);
++++++++++++++++++++lchild.parent+=+this;
++++++++++++++++++++allNodes.put(lchild,+lchild);
++++++++++++++++}+else+{
++++++++++++++++++++lchild.addNode(i,+allNodes);
++++++++++++++++}
++++++++++++}
++++++++}

++++++++@Override
++++++++public+boolean+equals(Object+obj)+{
++++++++++++return+((Node)+obj).value+==+value;
++++++++}

++++++++@Override
++++++++public+int+hashCode()+{
++++++++++++return+value;
++++++++}

++++++++@Override
++++++++public+String+toString()+{
++++++++++++return+String.valueOf(value);
++++++++}
++++}
}|code-block|syntax|javascript|1348994|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

here is DP implementation for BT distance. Not optimal, but interesting. 
it creates the tree 1st, with an input array.

<pre><code>import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by juanmf on 05/02/17.
 */
public class Main2 {
 /**
 * {50, 60, 30, 10, 20, 40} will form a Node Structure as follows
 * 5
 * ├─L─ 3
 * │   ├─L─ 1
 * │   │   └─R─ 2
 * │   └─R─ 4
 * └─R─ 6
 * L: left
 * R: Right
 * Path should be: [4, 3, 1, 2]
 * steps: 3 &lt;- output
 *
 * @param args
 */
 public static void main(String[] args) {
 int i = pathSteps(new int[] {50, 60, 30, 10, 20, 40}, 6, 20, 60);
 System.out.println(i);
 }

 private static int pathSteps(int[] ints, int n, int from, int to) {
 Node root = null;
 Map&lt;Node, Node&gt; allNodes = new HashMap&lt;&gt;();

 for (int i: ints) {
 if (root == null) {
 root = new Node(i);
 allNodes.put(root, root);
 }
 root.addNode(i, allNodes);
 }
 Map&lt;Node, List&lt;Node&gt;&gt; cache = new HashMap&lt;&gt;();

 Node fromN = new Node(from);
 Node toN = new Node(to);

 if (! allNodes.containsKey(fromN) || ! allNodes.containsKey(toN)) {
 return -1;
 }
 fromN = allNodes.get(fromN);
 toN = allNodes.get(toN);

 List&lt;Node&gt; path = traverse(fromN, toN, cache);
 return path.size() - 1;
 }

 private static List&lt;Node&gt; traverse(Node fromN, Node toN, Map&lt;Node, List&lt;Node&gt;&gt; cache) {

 if(cache.containsKey(fromN)) {
 System.out.println("cache Hit: " + fromN);

 return cache.get(fromN);
 }
 System.out.println("visiting: " + fromN);
 if (fromN == null || fromN.visited) {
 return new ArrayList&lt;&gt;();
 }
 if (fromN.equals(toN)) {
 List&lt;Node&gt; target = new ArrayList&lt;&gt;();
 target.add(toN);
 return target;
 }
 fromN.visited = true;

 List&lt;Node&gt; parentWay = new ArrayList&lt;&gt;();
 List&lt;Node&gt; lchildWay = new ArrayList&lt;&gt;();
 List&lt;Node&gt; rchildWay = new ArrayList&lt;&gt;();

 parentWay.addAll(traverse(fromN.parent, toN, cache));
 lchildWay.addAll(traverse(fromN.lchild, toN, cache));
 rchildWay.addAll(traverse(fromN.rchild, toN, cache));

 List&lt;Node&gt; shortest = getShortestList(getShortestList(parentWay, lchildWay), rchildWay);

 cache.put(fromN, shortest);
 if (! shortest.isEmpty()) {
 shortest.add(fromN);
 }
 fromN.visited = false;
 System.out.println(shortest);
 return shortest;
 }

 private static List&lt;Node&gt; getShortestList(List&lt;Node&gt; l1, List&lt;Node&gt; l2 ) {
 List&lt;Node&gt; shortest = null;
 if (l1 != null &amp; l2 != null) {
 if (l1.isEmpty()) {
 shortest = l2;
 } else if (l2.isEmpty()) {
 shortest = l1;
 } else {
 shortest = l1.size() &lt; l2.size() ? l1 : l2;
 }
 } else if (l1 == null) {
 shortest = l2;
 } else if (l2 == null) {
 shortest = l1;
 }
 return shortest;
 }

 private static class Node {
 Node parent;
 Node lchild;
 Node rchild;

 final int value;
 public boolean visited;

 private Node(int value) {
 this.value = value;
 }

 public void addNode(int i, Map&lt;Node, Node&gt; allNodes) {
 if (i &gt; value) {
 if (null == rchild) {
 rchild = new Node(i);
 rchild.parent = this;
 allNodes.put(rchild, rchild);
 } else {
 rchild.addNode(i, allNodes);
 }
 }
 if (i &lt; value) {
 if (null == lchild) {
 lchild = new Node(i);
 lchild.parent = this;
 allNodes.put(lchild, lchild);
 } else {
 lchild.addNode(i, allNodes);
 }
 }
 }

 @Override
 public boolean equals(Object obj) {
 return ((Node) obj).value == value;
 }

 @Override
 public int hashCode() {
 return value;
 }

 @Override
 public String toString() {
 return String.valueOf(value);
 }
 }
}
</code></pre>

How do I find the distance between two nodes in a binary tree? Equivalently, what algorithms are there for finding the most recent common ancestor (lowest common ancestor) of two nodes?

Looking for fast algorithm to find distance between two nodes in binary tree

如何找到二叉树中两个节点之间的距离？同样，有什么算法可以找到两个节点的最新共同祖先(最低共同祖先)？

问寻找二叉树中两节点间距离的快速算法
EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问寻找二叉树中两节点间距离的快速算法EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问寻找二叉树中两节点间距离的快速算法
EN