Day17 二叉树part07| LeetCode 235. 二叉搜索树的最近公共祖先 ，701.二叉搜索树中的插入操作 ，450.删除二叉搜索树中的节点

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

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

• 利用二叉搜索树的特性——有序树，可知，
  • 如果中间节点是p和q的公共节点，那个中间节点的数值一定在[p,q]区间
  • 因此，从根节点往下搜索，遇到的第一个位于[p,q]或[q,p]区间的节点就是最近公共祖先

class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
        {

        if(root==null) return null;
        if(root.val>p.val&&root.val>q.val)//左
        {
            TreeNode left=lowestCommonAncestor(root.left,p,q);
           if(left!=null) return left;
        }
        //右
            if(root.val<p.val&&root.val<q.val)
         {
            TreeNode right=lowestCommonAncestor(root.right,p,q);
            if(right!=null)
                return right;
            }

            //中
            return root;

        }
    }

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

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

  class Solution {

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

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

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

• 删除情况：

  1. 没找到删除的节点

  2. 删除的节点的左右子树都为空（叶子节点）

  3. 删除节点的左子树为空，右子树不为空

  4. 节点的右子树为空，左子树不为空

  5. 删除节点的左右子树都不为空

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

            /*终止条件*/
            //没找到删除节点
            if(root==null) return null;
            //找到删除节点
            if(root.val==key)
            {
                //删除节点为叶子节点
                if(root.left==null&&root.right==null)
                {
                    return null;
                }
                //删除节点的左子树为空，右子树不为空
               else if(root.left!=null&&root.right==null)
                {
                        return root.left;
                }
                //删除节点的右子树为空，左子树不为空
               else if(root.right!=null&&root.left==null)
                {
                        return root.right;
                }
                //删除节点的左右子树都不为空
                else
                {

                    //右孩子继位
                        TreeNode cur=root.right;
                        while(cur.left!=null) cur=cur.left;
                        cur.left=root.left;

                        //此时为左为空，右不为空
                    return root.right;
                }
            }
            /*单层递归*/
            if(key<root.val)
            {
                root.left=deleteNode(root.left,key);
            }
            else
            {
                root.right=deleteNode(root.right,key);
            }
            return  root;

        }
    }