235.md

✏️Leetcode之PHP版题目解析（237. Delete Node in a Linked List）

2020-04-12 吴亲库里 库里的深夜食堂

---

✏️描述

给定一棵二叉查找树和两个节点,求出这两个节点最近的公共祖先(一个节点也可以是它自己的祖先)

---

✏️题目实例

​

---

✏️题目分析

两个节点出现的位置无非有三种情况:

一个在左子树一个右子树(可能不是一个层级的节点)

全在左子树

全在右子树

​

假设现在在节点2这个位置,给定的p,q节点分别是3,5,这时候判断发现3,5 都大于2,此时我们知道他的公共祖先肯定出现在右子树(包括有可能是2),但是不能确定,所以就需要进入下一层,反之,在左子树上也是同样的道理

✏️递归实现

       /**
        * Definition for a binary tree node.
        * class TreeNode {
        *     public $val = null;
        *     public $left = null;
        *     public $right = null;
        *     function __construct($value) { $this->val = $value; }
        * }
        */
       
       class Solution {
           /**
            * @param TreeNode $root
            * @param TreeNode $p
            * @param TreeNode $q
            * @return TreeNode
            */
           function lowestCommonAncestor($root, $p, $q) {
               $parentVal=$root->val;
               $pVal=$p->val;
               $qVal=$q->val;
               if($pVal>$parentVal && $qVal>$parentVal){
                 return  $this->lowestCommonAncestor($root->right,$p,$q);
               }else if($pVal<$parentVal && $qVal<$parentVal){
                 return  $this->lowestCommonAncestor($root->left,$p,$q);
               }else{
                 return $root;
               }
               
           }
       }

✏️迭代实现

    /**
     * @param TreeNode $root
     * @param TreeNode $p
     * @param TreeNode $q
     * @return TreeNode
     */
    function lowestCommonAncestor($root, $p, $q) {
        $pVal=$p->val;
        $qVal=$q->val;
        $temp=$root;
        while($temp !=null){
            if($pVal > $temp->val && $qVal>$temp->val){
                $temp=$temp->right;
            }else if ($pVal<$temp->val && $qVal < $temp->val){
                $temp=$temp->left;
            }else{
                return $temp;
            }
        }
        return null;
    }

---

联系

​