LeetCode236. 二叉树的最近公共祖先

你的名字 2023-01-22 12:51 127阅读 0赞

题目难度：中等  
题目描述：

> 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点  
> p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70 1]

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { 
            if(root==NULL){ 
                return root;
            }
            if(root==p||root==q){ 
                return root;
            }
            TreeNode*left =lowestCommonAncestor(root->left,p,q);
            TreeNode*right =lowestCommonAncestor(root->right,p,q);
            if(left&&right){ 
                return root;
            }else if(left!=NULL){ 
                return left;
            }else if(right!=NULL){ 
                return right;
            }
            return NULL;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]: /images/20221020/a6f883bfd0444364bca6966233843c32.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70 1]: /images/20221020/d77e841b97b74ba79a9b5914ffe78ab3.png

LeetCode236. 二叉树的最近公共祖先

发表评论取消回复

还没有评论，来说两句吧...

相关阅读