p235

发表于 | 分类于 |

LeetCode p235 Lowest Common Ancestor of a Binary Search Tree 题解

1.题目：

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

    _______6______
   /              \
___2__          ___8__

/ \ / \
0 _4 7 9
/ \
3 5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

题意：

输入一个二叉查找树，在输入两个子树，找出这两个子树最近的公共节点。

2.解题思路:

见代码。。。十分暴力的解法了TUT。。。【捂脸逃

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
       List<TreeNode> a = new ArrayList<TreeNode>();
		List<TreeNode> b = new ArrayList<TreeNode>();
		TreeNode head = root;
		for (;;) {
			if (root.val == p.val) {
				a.add(root);
				break;
			} else {
				if (root.val > p.val) {
					a.add(root);
					root = root.left;
				} else {
					a.add(root);
					root = root.right;
				}
			}
		}
		root = head;
		for (;;) {
			if (root.val == q.val) {
				b.add(root);
				break;
			} else {
				if (root.val > q.val) {
					b.add(root);
					root = root.left;
				} else {
					b.add(root);
					root = root.right;
				}
			}
		}
		int alen = a.size() - 1;
		int blen = b.size() - 1;
		root = head;
		HashSet<Integer> hashSet = new HashSet<Integer>();
		for (; alen > -1; alen--) {

			hashSet.add(a.get(alen).val);

		}
		for (; blen > -1; blen--) {

			if (hashSet.contains(b.get(blen).val)) {

				root = b.get(blen);
				break;
			}
			hashSet.add(b.get(blen).val);
		}
		//System.out.println(root.val);
		return root;
    }
}

4.一些总结：