一、題目大意
給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先，
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個節點 p、q，最近公共祖先表示為一個節點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先），”
示例 1：
輸入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出：3
解釋：節點 5 和節點 1 的最近公共祖先是節點 3 ，
示例 2：
輸入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出：5
解釋：節點 5 和節點 4 的最近公共祖先是節點 5 ，因為根據定義最近公共祖先節點可以為節點本身，
示例 3：
輸入：root = [1,2], p = 1, q = 2
輸出：1
提示：
-
樹中節點數目在范圍 [2, 105] 內，
-
-109 <= Node.val <= 109
-
所有 Node.val 互不相同 ，
-
p != q
-
p 和 q 均存在于給定的二叉樹中，
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
二、解題思路
這是 二叉搜索樹的最近公共祖先 這題的衍生題，這道題是普通的二叉樹，不是二叉搜索樹，所以就不能利其特有的性質，只能在二叉樹中來搜索p和q，然后從路徑中找到最后一個相同的節點即為父節點，可以用遞回來實作，在遞回函式中，首先看當前節點是否為空，若為空則直接回傳空；若為p或q中的任一個，也直接回傳當著節點；否則的話就對其左右子節點分別呼叫遞回函式，這道題限制了p和q一定都在二叉樹中存在，那么如果當前節點不等于p或q，p和q要么分別位于左右子樹中，要么同時位于左子樹，或者同時位于右子樹：
若p和q分別位于左右子樹中，對于左右子節點呼叫遞回函式，分別回傳p和q節點的位置，而當前節點正好是p和q的最小共同父節點，直接回傳當前節點即可
若p和q同時位于左子樹，有兩種情況，一種是left會回傳p和q中較高的那個位置，而right會回傳空，所以最侄訓傳非空的left即可，還有一種情況是回傳p和q最小父節點，就是說當前節點的左子樹中的某個節點才是p和q的最小父節點，會被回傳，
若p和q同時位于右子樹，和位于同時位于左子樹類似，
三、解題方法
3.1 Java實作
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
return left != null ? left : right;
}
}
四、總結小記
- 2022/10/10 世界之大，無奇不有
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/513029.html
標籤：其他