2023.7.11
? ? ? ? 這道題是道面試高頻題,并且有點抽象。
????????首先確定終止條件。如果根節(jié)點為空,或者其中一個節(jié)點是根節(jié)點本身(即 p == root
或 q == root
),那么根節(jié)點就是它們的最低共同祖先,因此我們直接返回根節(jié)點 root
。?
????????接下來,遞歸調(diào)用 lowestCommonAncestor
方法來查找左子樹和右子樹中 是否存在p、q節(jié)點,若存在則返回相應(yīng)節(jié)點。
? ? ? ? 最后,根據(jù)左子樹和右子樹中返回的結(jié)果來確定最終的最低共同祖先。
? ? ? ? 細(xì)節(jié)都在代碼中:
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// 中止條件
if(root==p || root==q || root==nullptr) return root;
//遞歸地 從根節(jié)點向下搜索p、q是否存在于當(dāng)前節(jié)點的左右子樹中,若存在則返回相應(yīng)節(jié)點。
TreeNode* left = lowestCommonAncestor(root->left,p,q);
TreeNode* right = lowestCommonAncestor(root->right,p,q);
//左右子樹返回值都不為空, 由于值唯一左右子樹的返回值就是p和q, 此時root為最近公共祖先。
if(left!=nullptr && right!=nullptr) return root;
//左右子樹不是均不為空,那么此時兩節(jié)點存在包含關(guān)系:即一個節(jié)點在另一個節(jié)點的子樹中,此時最近公共祖先就是不為空的那個節(jié)點。
return left==nullptr? right : left;
}
};
? ? ? ? 需要多刷幾次的題。文章來源:http://www.zghlxwxcb.cn/news/detail-550208.html
2023.11.11????????
? ? ? ? java二刷。文章來源地址http://www.zghlxwxcb.cn/news/detail-550208.html
/**
* 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 || 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 null;
if(left == null) return right;
if(right == null) return left;
return root;
}
}
到了這里,關(guān)于leetcode 236. 二叉樹的最近公共祖先的文章就介紹完了。如果您還想了解更多內(nèi)容,請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!