算法训练营Day22(二叉树)

相对于?二叉树的最近公共祖先?本题就简单一些了，因为?可以利用二叉搜索树的特性。?

我的题解，，前序遍历做的，用了二叉搜索树的特性，但是只用了一半。。还是挺慢

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || root==p || root==q)return root;
        if((root.val>q.val&&root.val<p.val) || (root.val<q.val&&root.val>p.val))return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left!=null)return left;
        return right;
    }
}

卡哥的递归法，在我的基础上加了一些。我的好像还比他的快，

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return root;
        if(root.val>p.val&&root.val>q.val) return lowestCommonAncestor(root.left,p,q);
        if(root.val<p.val&&root.val<q.val) return lowestCommonAncestor(root.right,p,q);
        return root;
    }
}

迭代法，也好理解的一批

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(true){
            if(root.val>p.val&&root.val>q.val){
                root = root.left;
            }else if(root.val<p.val&&root.val<q.val){
                root = root.right;
            }else{
                break;
            }
        }
        return root;
    }
}

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

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null) return new TreeNode(val);
        TreeNode res = root;
        while(true){
            if(val<root.val){
                if(root.left!=null){
                    root=root.left;
                    continue;
                }
                root.left = new TreeNode(val);
                break;
            }else if(val>root.val){
                if(root.right!=null){
                    root=root.right;
                    continue;
                }
                root.right = new TreeNode(val);
                break;
            }
        }
        return res;
    }
}

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null) return null;
        if(root.val == key){
            //左为null右为null
            if(root.left==null&&root.right==null){
                return null;
            }
            //左不为null右为null
            else if(root.left!=null&&root.right==null){
                return root.left;
            }
            //左为null右不为null
            else if(root.left==null&&root.right!=null){
                return root.right;
            }
            //左右都不为null
            else{
                //当前要删的节点的右孩子
                TreeNode cur = root.right;
                //找右孩子的最小值（最左孩子）
                while(cur.left!=null)cur=cur.left;
                //root左孩子给cur
                cur.left = root.left;
                //结果返回右孩子
                return root.right;
            }
        }

        //到这里只是写完了终止条件
        //开始赋值，递归的单层逻辑
        if(key<root.val) root.left = deleteNode(root.left,key);
        if(key>root.val) root.right = deleteNode(root.right,key);
    
        return root;
    }
}