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;
    }
};

? ? ? ? 需要多刷幾次的題。

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)！