找建筑类工作哪个网站好,整个网站开发框架流程,成都市高新区规划建设局网站,wordpress分类图片【试题描述】 求二叉树中任意两个节点的最近公共祖先也称为LCA问题#xff08;Lowest Common Ancestor#xff09;。 二叉查找树 如果该二叉树是二叉查找树#xff0c;那么求解LCA十分简单。 基本思想为#xff1a;从树根开始#xff0c;该节点的值为t#xff0c;如果t大… 【试题描述】 求二叉树中任意两个节点的最近公共祖先也称为LCA问题Lowest Common Ancestor。 二叉查找树 如果该二叉树是二叉查找树那么求解LCA十分简单。 基本思想为从树根开始该节点的值为t如果t大于t1和t2说明t1和t2都位于t的左侧所以它们的共同祖先必定在t的左子树中从t.left开始搜索如果t小于t1和t2说明t1和t2都位于t的右侧那么从t.right开始搜索如果t1t t2说明t1和t2位于t的两侧那么该节点t为公共祖先。 如果t1是t2的祖先那么应该返回t1的父节点同理如果t2是t1的祖先应该返回t2的父节点。 【参考代码】 1 public int query(Node t1, Node t2, Node t) {2 int left t1.value;3 int right t2.value;4 Node parent null;5 6 if (left right) {7 int temp left;8 left right;9 right temp;
10 }
11
12 while (true) {
13 if (t.value left) {
14 parent t;
15 t t.right;
16 } else if (t.value right) {
17 parent t;
18 t t.left;
19 } else if (t.value left || t.value right) {
20 return parent.value;
21 } else {
22 return t.value;
23 }
24 }
25 } 普通二叉树 算法思想如果一个节点的左子树包含pq中的一个节点右子树包含另一个则这个节点就是pq的最近公共祖先。 【参考代码】 解法一 1 public static Node findNCA(Node root, Node p, Node q)2 {3 if (isintree(root.left, p) isintree(root.left, q))4 return findNCA(root.left, p, q);5 if (isintree(root.right, p) isintree(root.right, q))6 return findNCA(root.right, p, q);7 return root;8 }9
10 public static boolean isintree(Node root, Node node)
11 {
12 if (root null)
13 return false;
14 if (root node)
15 return true;
16 return isintree(root.left, node) || isintree(root.right, node);
17 } 解法二 1 static int TWO_NODES_FOUND 2;2 static int ONE_NODES_FOUND 1;3 static int NO_NODES_FOUND 0;4 5 public static int covers(Node root, Node p, Node q)6 {7 int ret NO_NODES_FOUND;8 if (root null)9 return ret;
10 if (root p || root q)
11 ret 1;
12 ret covers(root.left, p, q);
13 if (ret TWO_NODES_FOUND)
14 return ret;
15 return ret covers(root.right, p, q);
16 }
17
18 private static Node findNCA(Node root, Node p, Node q)
19 {
20 if (q p (root.left q || root.right q))
21 return root;
22 int nodesFromLeft covers(root.left, p, q);
23 if (nodesFromLeft TWO_NODES_FOUND)
24 {
25 if (root.left p || root.left q)
26 return root.left;
27 else
28 return findNCA(root.left, p, q);
29 } else if (nodesFromLeft ONE_NODES_FOUND)
30 {
31 if (root p)
32 return p;
33 else if (root q)
34 return q;
35 }
36
37 int nodesFromRight covers(root.right, p, q);
38 if (nodesFromRight TWO_NODES_FOUND)
39 {
40 if (root.right p || root.right q)
41 return root.right;
42 else
43 return findNCA(root.right, p, q);
44 } else if (nodesFromRight ONE_NODES_FOUND)
45 {
46 if (root p)
47 return p;
48 else if (root q)
49 return q;
50 }
51
52 if (nodesFromLeft ONE_NODES_FOUND
53 nodesFromLeft ONE_NODES_FOUND)
54 return root;
55 else
56 return null;
57 } 解法三网上版本 1 public static int FindNCA(Node root, Node a, Node b, Node out)2 {3 if (root null)4 return 0;5 if (root a || root b)6 return 1;7 8 int iLeft FindNCA(root.left, a, b, out);9 if (iLeft 2)
10 return 2;
11
12 int iRight FindNCA(root.right, a, b, out);
13 if (iRight 2)
14 return 2;
15
16 if (iLeft iRight 2)
17 out root;
18
19 return iLeft iRight;
20 } 这个网上说输出时 当为2时才输出但是为2时不能判断如果其中一个是另一个的父亲节点情况。所以理论上应该改为当返回结果大于0时就可以输出结果。但是不太确定正确性应该程序是正确的。 参考 http://blog.csdn.net/w397090770/article/details/7615447 转载于:https://www.cnblogs.com/WayneZeng/p/9290761.html
