代码随想录训练营第二十二天 ｜ 二叉树

今天是第22天，依旧还是二叉树

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

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return root;
        }
        if(root == p || root == q){
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null){
            return root;
        }
        if (left!=null){
            return left;
        }
        if(right != null){
            return right;
        }
        return null;
    }
}

和昨天的一道题可以用一样的代码去解决，如果要利用bst的特性的话，那就在left 和 right上加入对比root值的代码就可以了。

701. 二叉树中的插入操作

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null){
            return new TreeNode(val);
        }
        if(root.val < val){
            root.right = insertIntoBST(root.right, val);
        }else{
            root.left = insertIntoBST(root.left, val);
        }
        return root;
    }
}

找到空节点插入即可

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

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null){
            return null;
        }
        if(key < root.val){
            root.left = deleteNode(root.left, key);
            return root;
        }
        if(key > root.val){
            root.right = deleteNode(root.right, key);
            return root;
        }
        else{
            if(root.left == null){
                return root.right;
            }
            else if(root.right == null){
                return root.left;
            }
            else{
                TreeNode successor = min(root.right);
                successor.right = deleteMin(root.right);
                successor.left = root.left;
                return successor;
            }
        }
    }
    public TreeNode min(TreeNode node){
        if(node.left == null){
            return node;
        }
        return min(node.left);
    }
    TreeNode deleteMin(TreeNode node){
        if(node.left == null){
            return node.right;
        }
        node.left = deleteMin(node.left);
        return node;
    }
}

递归法

今天的题都是二叉搜索树，做完后可以掌握其特性