我的LeetCode代碼倉:https://github.com/617076674/LeetCode
原題連結:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
題目描述:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHLykEVPhXTq1EeRpHW4Z0MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnL2ETM5ETMzQTMyEjMwkTMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
知識點:二叉搜尋樹
思路:遞歸尋找二叉搜尋樹的最近公共祖先
如果給定q、p節點的值在root的值的兩側,即一個大于等于root值,一個小于等于root值,那麼root節點就是最近公共祖先。
如果p、q節點的值均小于等于root值,那麼遞歸地在左子樹中尋找。
如果p、q節點的值均大于等于root值,那麼遞歸地在右子樹中尋找。
時間複雜度和空間複雜度均是O(h),其中h為樹的高度。
JAVA代碼:
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(p.val <= root.val && q.val >= root.val) {
return root;
}else if(p.val >= root.val && q.val <= root.val) {
return root;
}else if(p.val <= root.val && q.val <= root.val) {
return lowestCommonAncestor(root.left, p, q);
}else {
return lowestCommonAncestor(root.right, p, q);
}
}
}
LeetCode解題報告: