代码随想录算法训练营第二十二天

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

本题相较于非BST的LCA求解要容易得多，因为每次递归时我们可以利用BST的性质判断出公共祖先节点的位置区间，因此就变得简洁的多。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
        // if root.val == q.val or p.val then no need to traverse
        if (root == null || root.val == q.val || root.val == p.val) {
            return root;
        }

        // if both q's and p's val are less than root.val then search the left side
        if (root.val > q.val && root.val > p.val) {
            return lowestCommonAncestor(root.left, p, q);
        }

        // if both q's and p's val are larger than root.val then search the right side
        if (root.val < q.val && root.val < p.val) {
            return lowestCommonAncestor(root.right, p, q);
        }

        // else it means that the two nodes are in both sides, no matter q is in left &&
        // p in the right or the reversed situation, just return root 
        return root;


    }
}

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

二叉搜索树的插入操作还是相对简单的，找到目标位置，插入即可，不涉及树结构的改变。

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {

        if (root == null) {
            root = new TreeNode (val);
        }else {
            insertRecursively(root, val);
        }

        return root;
    }

    // a helper function help us do the recursion 
    private void insertRecursively (TreeNode node, int val) {
       
        if (node == null) {
            return;
        }

        if (val < node.val) {
           if (node.left != null) {
            insertNode(node.left, val);
           }else {
            node.left = new TreeNode (val);
           }
        }

        if (val > node.val) {
            if (node.right != null) {
             insertNode(node.right, val);
            }else {
             node.right = new TreeNode (val);
            }
         }

    }
}

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

这道题还是挺有难度的，需要考虑很多种情况，主要是因为删除节点会对树的结构带来改变。

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {

        if (root == null) {
            return root;
        }
        List<Integer> list = new LinkedList<>();

        // if root is the node to delete
        if (root.val == key) {

            // if right branch is null then return left
            if (root.left != null && root.right == null) {
                return root.left;
            }

            // if left branch is null then return right
            if (root.left == null && root.right != null) {
                return root.right;
            }

            // if no children just return null
            if (root.left == null && root.right == null) {
                return null;
            }

            // else: it means that both child nodes exist
            
            // find the leftmost child of root's right branch
            TreeNode node = root.right;
            while (node.left != null) {
                node = node.left;
            }
            node.left = root.left; 
            return root.right;

        }else {
            if (root.val > key) {
                // we maintain that deleteNode returns the new node after deletion
                root.left = deleteNode(root.left, key);
            }else {
                root.right = deleteNode(root.right, key);
            }
        }
        return root;
    }
}