LeetCode235（二叉搜索树的最近公共祖先）

发表于 | 分类于 ，

题目：

　　给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

思路：

　　二叉树一般会用到递归或遍历。结合此题，由于该树是二叉搜索树，最近公共祖先节点的特点即其节点的值大于
等于p（左边）节点的值，小于等于q（右边）节点的值。由此可以写出递归或者循环代码。

代码：

1.递归：

1
2
3
4
5
6
7
8
9
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      if (p.val > root.val && q.val > root.val) {
	return lowestCommonAncestor(root.right, p, q);
}else if (p.val < root.val && q.val < root.val) {
	return lowestCommonAncestor(root.left, p, q);
}else {
	return root;
}
  }

2.循环：

1
2
3
4
5
6
7
8
9
10
11
12
13
 public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
 	TreeNode node = root;
 	while(node != null) {
 		if (p.val > node.val && q.val > node.val) {
	node = node.right;
}else if (p.val < node.val && q.val < node.val) {
	node = node.left;
}else {
	return node;
}
 	}
 	throw new RuntimeException("输入不合法");
 }

复杂度分析及总结：

1.递归：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。

2.循环：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。