代码随想录算法训练营第十八天 | leetcode：二叉搜索树最近公共祖先 ,二叉搜索树中插入操作,删除二叉搜索树节点

235. 二叉搜索树的最近公共祖先

解题方法

思路：题目给定的二叉树为二叉搜索树，也就是说当前树节点是有序的，则公共祖先一定是在[p,q]中间。当我们从上向下去递归遍历，第一次遇到 cur节点是数值在[q, p]区间中，那么cur就是 q和p的最近公共祖先。
解题：按照中序遍历，寻找[p，q]区间。遍历节点时，判断cur节点与 p,q的大小关系,大于的话则在左子树方向继续遍历。小于p和q的话则往右子树遍历。因为不知道p，q哪个大，所以两个都需要判断。剩下的情况，就是cur节点在区间[p,q]中，那么cur就是最近公共祖先了，直接返回cur。

code

递归法

class Solution {
    /**
     * @param TreeNode $root
     * @param TreeNode $p
     * @param TreeNode $q
     * @return TreeNode
     */
    function lowestCommonAncestor($root, $p, $q) {
        if($root == null) return null;
        //如果当前节点小于p与q则往左子树搜索
        if($root->val > $p->val && $root->val > $q->val){
            $left = $this->lowestCommonAncestor($root->left,$p,$q);
            if($left != null) return $left;
        }
        //如果当前节点大于p与q则往右子树搜索
        if($root->val < $p->val && $root->val < $q->val){
            $right = $this->lowestCommonAncestor($root->right,$p,$q);
            if($right != null) return $right;
        }
        return $root;
    }
}

迭代法

class Solution {
    /**
     * @param TreeNode $root
     * @param TreeNode $p
     * @param TreeNode $q
     * @return TreeNode
     */
    function lowestCommonAncestor($root, $p, $q) {
        while($root){
            if($root->val > $p->val && $root->val > $q->val){
                $root = $root->left;
            }elseif($root->val < $p->val && $root->val < $q->val){
                $root = $root->right;
            }else{
                return $root;
            }
        }
    }
}

701. 二叉搜索树中的插入操作

解题方法

思路：题目说到可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回 任意有效的结果 。那么就可以忽略需要改变树结构的结果，只考虑在叶子节点插入的情况。

解法：只考虑在叶子节点插入的情况，而给定二叉树又是二叉搜索树，则可以在遍历过程中判断当前节点与给定的要插入的数值value大小，来确定value需要插入到二叉搜索树的哪个叶子节点。也就是找到遍历的节点为null的时候，就是要插入节点的位置了，并把插入的节点返回。

code

递归法

class Solution {

    /**
     * @param TreeNode $root
     * @param Integer $val
     * @return TreeNode
     */
    function insertIntoBST($root, $val) {
        if($root == null){
            //遍历到需要插入的叶子节点，初始化为节点并返回，下面会有左子树或者右子树接住
            $node = new TreeNode($val);
            return $node;
        }
        //小于当前节点往左子树遍历
        if($val < $root->val){
            $root->left = $this->insertIntoBST($root->left,$val);
        }
        //大于当前节点往右子树遍历
        if($val > $root->val){
            $root->right = $this->insertIntoBST($root->right,$val);
        }
        return $root;
    }
}

迭代法（用到双指针）

class Solution {

    /**
     * @param TreeNode $root
     * @param Integer $val
     * @return TreeNode
     */
    function insertIntoBST($root, $val) {
        if ($root == NULL) {
            $node = new TreeNode($val);
            return $node;
        }
        $cur = $root;
        $parent = $root; // 这个很重要，需要记录上一个节点，否则无法赋值新节点
        //遍历到对应的叶子节点
        while ($cur != NULL) {
            //记录叶子节点,因为后续cur是遍历到null结束
            $parent = $cur;
            if ($cur->val > $val) $cur = $cur->left;
            else $cur = $cur->right;
        }
        //var_dump($cur);
        $node = new TreeNode($val);
        //判断当前val应该插入叶子节点的左边还是右边
        if ($val < $parent->val) $parent->left = $node;// 此时是用parent节点的进行赋值
        else $parent->right = $node;
        return $root;
    }
}

450. 删除二叉搜索树中的节点

解题方法

与上题插入节点不同，删除节点，情况更复杂。并且伴随二叉树的结构修改。需要理清楚每种删除情况。
删除节点有以下五种情况：

第一种情况：没找到删除的节点，遍历到空节点直接返回了找到删除的节点
第二种情况：左右孩子都为空（叶子节点），直接删除节点，返回NULL为根节点
第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

code

class Solution {

    /**
     * @param TreeNode $root
     * @param Integer $key
     * @return TreeNode
     */
    function deleteNode($root, $key) {
        /* 删除节点情况：
        * 1. 没找到删除节点
        * 2. 删除节点为叶子节点：左为空右为空
        * 3. 删除节点：左不为空，右为空
        * 4. 删除节点：左为空，右不为空
        * 5. 删除节点：左右都不为空
        */
        if($root == null) return null;
        //print_r($key);
        if($root->val == $key){
            if($root->left == null && $root->right == null){
                //删除叶子节点直接返回当前给父节点即可
                return null;
            }elseif($root->left != null && $root->right == null){
                //删除节点左子树不为空直接返回左子树给父节点即可
                return $root->left;
            }elseif($root->left == null && $root->right != null){
                //删除节点右子树不为空直接返回右子树给父节点即可
                return $root->right;
            }else{
                //左右都不为空，把当前节点左子树移植到当前节点右子树的最小左节点，最后返回右子树给父节点即可
                $cur = $root->right;
                while($cur->left != null){
                    //找到当前节点右子树的最小左节点
                    $cur = $cur->left;
                }
                //把当前节点的左子树给当前节点右子树的最小左节点
                $cur->left = $root->left;
                $root = $root->right;
                return $root;
            }
        }
        if($key < $root->val) $root->left = $this->deleteNode($root->left,$key);
        if($key > $root->val) $root->right = $this->deleteNode($root->right,$key);
        return $root;
    }
}