题目：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
练习地址
https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
参考答案
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode common = root;
while (common != null) {
if (common.val > p.val && common.val > q.val) {
common = common.left;
} else if (common.val < p.val && common.val < q.val) {
common = common.right;
} else {
return common;
}
}
return common;
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
练习地址
https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
参考答案
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == null || q == null) {
return null;
}
LinkedList<TreeNode> path1 = new LinkedList<>();
getNodePath(root, p, path1);
LinkedList<TreeNode> path2 = new LinkedList<>();
getNodePath(root, q, path2);
return getLastCommonNode(path1, path2);
}
private boolean getNodePath(TreeNode root, TreeNode node, LinkedList<TreeNode> path) {
if (root == null) {
return false;
}
path.add(root);
if (root == node) {
return true;
}
boolean found = getNodePath(root.left, node, path);
if (!found) {
found = getNodePath(root.right, node, path);
}
if (!found) {
path.removeLast();
}
return found;
}
private TreeNode getLastCommonNode(LinkedList<TreeNode> path1, LinkedList<TreeNode> path2) {
Iterator<TreeNode> iterator1 = path1.iterator();
Iterator<TreeNode> iterator2 = path2.iterator();
TreeNode last = null;
while (iterator1.hasNext() && iterator2.hasNext()) {
TreeNode node = iterator1.next();
if (node == iterator2.next()) {
last = node;
} else {
break;
}
}
return last;
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(logn)。
