3、二分搜索树.md

### 二分搜索树

#### [235. 二叉搜索树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/)

难度简单532收藏分享切换为英文接收动态反馈

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

[百度百科](https://baike.baidu.com/item/最近公共祖先/8918834?fr=aladdin)中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（**一个节点也可以是它自己的祖先**）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

![在这里插入图片描述](https://img-blog.csdnimg.cn/20210210230729177.png)


 

**示例 1:**

```
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。
```

**示例 2:**

```
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
```



**题解**

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

        boolean isPBigger = p.val >= q.val;
        if((isPBigger && p.val >= root.val && q.val <= root.val) 
                || (!isPBigger && q.val >= root.val && p.val <= root.val )){
            return root;
        }

        if(p.val > root.val && q.val > root.val){
            return  lowestCommonAncestor(root.right , p , q);
        }else {
            return lowestCommonAncestor(root.left , p , q);
        }

    }
    
}
```



#### [450. 删除二叉搜索树中的节点](https://leetcode-cn.com/problems/delete-node-in-a-bst/)

难度中等389收藏分享切换为英文接收动态反馈

给定一个二叉搜索树的根节点 **root** 和一个值 **key**，删除二叉搜索树中的 **key** 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

1. 首先找到需要删除的节点；
2. 如果找到了，删除它。

**说明：** 要求算法时间复杂度为 O(h)，h 为树的高度。

**示例:**

```
root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

    5
   / \
  4   6
 /     \
2       7

另一个正确答案是 [5,2,6,null,4,null,7]。

    5
   / \
  2   6
   \   \
    4   7
```



**题解**

```java
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode[] targets = getDeleteNode(root , key);
        if(targets == null){
            return root;
        }
        TreeNode parent = targets[0];
        TreeNode target = targets[1];

        if(target.right == null && target.left == null){
            if(parent == target){
                return null;
            }
            if(parent.left == target){
                parent.left = null;
            }else {
                parent.right = null;
            }
            return root;
        }

        int val;
        if(target.right != null){
            val = findMinValue(target.right);
        }else {
            val = findMaxValue(target.left);
        }

        deleteNode(root ,val);
        target.val = val;

        return root;
    }

    TreeNode[] getDeleteNode(TreeNode root , int key){
        TreeNode parent = root , child = root;
        while(child != null){
            if(key == child.val){
                return new TreeNode[]{parent , child};
            }else if(key > child.val){
                parent = child;
                child = child.right;
            }else {
                parent = child;
                child = child.left;
            }
        }

        return null;
    }

    int findMinValue(TreeNode root){
        while(root.left != null){
            root = root.left;
        }
        return root.val;
    }

    int findMaxValue(TreeNode root){
        while(root.right != null){
            root = root.right;
        }
        return root.val;
    }


}
```



#### [108. 将有序数组转换为二叉搜索树](https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/)

难度简单695收藏分享切换为英文接收动态反馈

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树*每个节点* 的左右两个子树的高度差的绝对值不超过 1。

**示例:**

```
给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5
```





**题解**

```java
class Solution {
    TreeNode root;
    public TreeNode sortedArrayToBST(int[] nums) {
        findMid(nums , 0 , nums.length - 1);
        return root;
    }

    void findMid(int[] nums , int startIdx , int endIdx){
        if(startIdx > endIdx){
            return;
        }
        int mid = (startIdx + endIdx) / 2;
        addNode(nums[mid]);

        findMid(nums , startIdx , mid - 1);
        findMid(nums , mid + 1 , endIdx);
    }

    void addNode(int val){
        if(root == null){
            root = new TreeNode(val);
            return;
        }

        TreeNode node = root;
        while(true){
            if(node.val >= val){
                if(node.left == null){
                    node.left = new TreeNode(val);
                    break;
                }
                node = node.left;
            }else {
                if(node.right == null){
                    node.right = new TreeNode(val);
                    break;
                }
                node = node.right;
            }
        }
    }
}
```



#### [236. 二叉树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)

难度中等928收藏分享切换为英文接收动态反馈

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

[百度百科](https://baike.baidu.com/item/最近公共祖先/8918834?fr=aladdin)中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（**一个节点也可以是它自己的祖先**）。”

 

**示例 1：**

![在这里插入图片描述](https://img-blog.csdnimg.cn/20210210230657799.png)


```
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
```

**示例 2：**

![在这里插入图片描述](https://img-blog.csdnimg.cn/20210210230712731.png)


```
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
```

**示例 3：**

```
输入：root = [1,2], p = 1, q = 2
输出：1
```



**题解**

```java
class Solution {
    TreeNode res ;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        getFindNum(root , p , q);
        return res;
    }

    int getFindNum(TreeNode root, TreeNode p, TreeNode q){
        if(root == null){
            return 0;
        }
        
        int findNum = getFindNum(root.left , p , q) + getFindNum(root.right, p , q);
        if(findNum == 2){
            res = root;
            return 3;
        }

        if(root.val == p.val || root.val == q.val){
            if(findNum == 1){
                res = root;
                return 3;
            }else {
                return findNum + 1;
            }
        }
        
        return findNum;
    }
}
```