一、題目大意
給定一個二叉搜索樹, 找到該樹中兩個指定節點的最近公共祖先，
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先），”
例如，給定如下二叉搜索樹: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
輸出: 6
解釋: 節點 2 和節點 8 的最近公共祖先是 6，
示例 2:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
輸出: 2
解釋: 節點 2 和節點 4 的最近公共祖先是 2, 因為根據定義最近公共祖先節點可以為節點本身，
說明:
-
所有節點的值都是唯一的，
-
p、q 為不同節點且均存在于給定的二叉搜索樹中，
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
二、解題思路
求二叉樹的最小共同父節點，可以用遞回來求解，同志二叉搜索樹的特點是左<根<右，所以根節點的值一直都是中間值，大于左子樹的所有節點值，小于右子樹的所有節點值，我們可以做如下判斷，如果根節點的值大于p和q之間的較大值，說明q和q都在左子樹中，那么此時我們就進入根節點的左子節點繼續uxjv，如果根節點小于p和q之間的較小值，說明p和q都在右子樹中，那么此時我們就進入根節點的右子節點繼續遞回，如果都不是，則說明當前根節點就是是耳濡目染共同父節點，直接回傳即可，
三、解題方法
3.1 Java實作
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return root;
}
if (root.val > Math.max(p.val, q.val)) {
return lowestCommonAncestor(root.left, p, q);
} else if (root.val < Math.min(p.val, q.val)) {
return lowestCommonAncestor(root.right, q, q);
} else {
return root;
}
}
}
四、總結小記
- 2202/10/4 假期疫情瞬息萬變
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/510952.html
標籤：其他
上一篇：東深電子Java面試總結
下一篇：小程式逆向