导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-235.Lowest Common Ancestor of a Binary Search Tree

题目

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(https://en.wikipedia.org/wiki/Lowest_common_ancestor): “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).”

翻译

给出一个二叉搜索树(BST),寻找给出两个节点在BST上的最小公共祖先(LCA)。
根据Wikipedia上对LCA的定义(https://en.wikipedia.org/wiki/Lowest_common_ancestor) :“对于两个节点v和w,在树T中,深度最小的、v和w同时为其后代的节点,定义为v和w的最小公共祖先(节点是自身的后代)”。
    6
   /  \
  2    8
 / \   /  \
0   4 7   9
   / \
  3  5
例如,2和8的最小公共祖先(LCA)是6,2和4的最小公共祖先是2,因为根据LCA的定义节点可以是自身的后代。

利用二叉搜索树的性质,左子树上的所有节点值都比根节点值小,右子树上所有节点值都比根节点大,递归判断:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 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) {
if (root == null || p == null || q == null)
return null;

if (p.val < root.val && q.val < root.val)
return lowestCommonAncestor(root.left, p, q);

if (p.val > root.val && q.val > root.val)
return lowestCommonAncestor(root.right, p, q);

return root;
}
}

另外,本题有两个追加条件:
1、如果p和q不在树上;
2、如果是一颗普通二叉树。
对于1,我们可以编写一个函数,递归查找节点,判断是否在树上,任何一个节点不在树上,返回null即可。
对于2,方法为编写一个函数,记录从根节点到该节点的路径上经过的所有节点,然后遍历从根节点分别到p和q的路径节点,直到路径节点不同或其中一条路径走完为止,返回最后一个相同路径节点。在寻找路径的同时,可以解决问题1。
代码如下:

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
/**
* 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> pPath = new ArrayList<TreeNode>();
List<TreeNode> qPath = new ArrayList<TreeNode>();

if (!getPath(root, p, pPath) || !getPath(root, q, qPath))
return null;

TreeNode lowestCommonAncestor = root;
for (int i = 1; i < pPath.size() && i < qPath.size(); i++) {
if (pPath.get(i) == qPath.get(i))
lowestCommonAncestor = pPath.get(i);
else break;
}

return lowestCommonAncestor;

}

public boolean getPath(TreeNode root, TreeNode t, List<TreeNode> path) {
path.add(root);

if (root == null)
return false;

// 是否为根
if (root == t)
return true;

// 是否在左子树
if (getPath(root.left, t, path))
return true;
else path.remove(path.size() - 1);

// 是否在右子树
if (getPath(root.right, t, path))
return true;
else path.remove(path.size() - 1);

return false;
}
}

参考:
http://www.cnblogs.com/lihaozy/archive/2012/12/03/2799408.html
http://blog.csdn.net/xudli/article/details/46838747