算法训练（leetcode）二刷第十七天 | 235. 二叉搜索树的最近公共祖先、701. 二叉搜索树中的插入操作、*450. 删除二叉搜索树中的节点

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

leetcode题目地址

二叉搜索树比普通树更容易搜索，因为其具有左小右大的性质。

时间复杂度： $O(H)$
空间复杂度： $O(n)$

// java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {

    public TreeNode findAncestor(TreeNode root, TreeNode p, TreeNode q){
        if(root == null) return root;
        // 比较大值大 向左走
        if(root.val > q.val){
            TreeNode left = findAncestor(root.left, p, q);
            if(left != null) return left;
        }
        // 比较小值小 向右走
        if(root.val < p.val) {
            TreeNode right = findAncestor(root.right, p, q);
            if(right != null) return right;
        }
        // 当前节点处于二者中间 即为最近公共祖先
        return root;

    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p.val > q.val){
            TreeNode temp = p;
            p = q;
            q = temp;
        }
        return findAncestor(root, p, q);
    }
}

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

leetcode题目地址

利用二叉搜索树性质插入。

时间复杂度： $O(H)$
空间复杂度： $O(n)$

递归

// java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void insert(TreeNode root, int val){
        if(root == null) return;
        if(val > root.val && root.right == null){
            root.right = new TreeNode(val);
            return;
        }
        if(val < root.val && root.left == null){
            root.left = new TreeNode(val);
            return;
        }
        if(val > root.val) insert(root.right, val);
        if(val < root.val) insert(root.left, val);
    }

    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null) return new TreeNode(val);
        insert(root, val);
        return root;
    }
}

迭代一

// java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null) return new TreeNode(val);
        TreeNode cur = root;
        TreeNode parent = root;
        while(cur != null){
            parent = cur;
            if(cur.val > val) cur = cur.left;
            else cur = cur.right;
        }
        cur = new TreeNode(val);
        if(val > parent.val) parent.right = cur;
        else parent.left = cur;
        return root;
    }
}

迭代二

// java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null) return new TreeNode(val);
        TreeNode cur = root;
        while(true){
            if(cur.val > val) {
                if(cur.left == null) {
                    cur.left = new TreeNode(val);
                    break;
                }
                cur = cur.left;
            } else {
                if(cur.right == null){
                    cur.right = new TreeNode(val);
                    break;
                }
                cur = cur.right;
            }
        }
        return root;
    }
}

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

leetcode题目地址

思路一

使用二叉搜索树的删除操作在数据结构中的解题思路：

1. 若要删除的结点左右子树均为空，则直接删除。
2. 若要删除结点左子树为空右子树不空，则用右子树的最左结点替换当前要删除结点，然后递归删除右子树的最左节点。
3. 若要删除结点左子树不空右子树为空，则用左子树的最右结点替换当前要删除结点，然后递归删除左子树的最右节点。
4. 若要删除结点的左右子树均不为空，则按照2、3中的任一规则进行删除。

也就是说，只有递归到叶节点（左右子树均空）才会物理删除结点，有孩子时只会对值进行替换，然后继续递归。

依照上述思路，代码如下：

时间复杂度： $O(logn)$
空间复杂度： $O(logn)$

// java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
	// 标识根节点
    boolean flag;
    // cur: 要删除的结点  parent：cur的父节点
    public void delete(TreeNode cur, TreeNode parent){
        // 叶子节点
        if(cur.left == null && cur.right == null){
            // 根节点
            if(parent == null) {
                this.flag = true;
                return;
            }
            // 是父节点的左子树则将左子树置空
            if(parent.left == cur) parent.left = null;
            // 反之，置空右子树
            else parent.right = null;
            
        }else if(cur.left == null){
            // 左空右不空 取右子树最左节点
            TreeNode node = cur.right;
            TreeNode nodeParent = cur;
            while(node.left != null){
                nodeParent = node;
                node = node.left;
            }
            cur.val = node.val;
            delete(node, nodeParent);
            
        } else{
            // 右空左不空/左右都不空  取左子树最右节点
            TreeNode node = cur.left;
            TreeNode nodeParent = cur;
            while(node.right != null){
                nodeParent = node;
                node = node.right;
            }
            cur.val = node.val;
            delete(node, nodeParent);
        }
    }
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode cur = root;
        TreeNode parent = null;
        // 利用搜索树性质查找要删除结点
        while(cur != null && cur.val != key){
            parent = cur;
            if(key > cur.val) cur = cur.right;
            else cur = cur.left;
        }
        
        // 找到
        if(cur!=null){
            // 标记树中只有一个节点且要删除的就是根节点
            this.flag = false;
            delete(cur, parent);
            // 要删除的是根且树中仅有根这一个节点，则将根节点置空
            if(this.flag) root = null;
        }
        return root;
    }
}