LeetCode 236. Lowest Common Ancestor of a Binary Tree

题解

求解最近公共父节点,比较经典的题目。
思路是二路dfs。沿着左右下行,终结条件是 空节点 或者 root==(p or q)。
那么此时,Left Right 有三种情况

  1. 均非空:左右两子树刚好各有一个目标节点,此时root就是父节点。
  2. 一空一非空:空端子树没有目标节点,非空一端子树为父节点。
  3. 双空:舍弃。

为什么这样可行,因为递归作用下,但凡返回的是非空那么该子树必然至少含有一个目标节点。
若有疑问,可举例理解。


Code
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL||root==q||root==p){
            return root;
        }
        
        TreeNode *l=lowestCommonAncestor(root-left,p,q);
        TreeNode *r=lowestCommonAncestor(root-right,p,q);
        
        if(l!=NULL r!=NULL ) return root;
        
        return (l!=NULL ? l:r);
    }
};
最新回复(0)
/jishuytddIVoibuzy_2FIDUnM8vkDY_2B_2FEoNdw1tqI4Erw_3D_3D4858373
8 简首页