【LeetCode】二叉树问题：二分搜索树

快来打我* 2022-10-29 09:12 192阅读 0赞

### 二分搜索树 ###

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

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

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

[百度百科][Link 1]中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（**一个节点也可以是它自己的祖先**）。”

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

![在这里插入图片描述][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, 因为根据定义最近公共祖先节点可以为节点本身。

**题解**

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. 删除二叉搜索树中的节点][450.] ####

难度中等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

**题解**

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. 将有序数组转换为二叉搜索树][108.] ####

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

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

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

**示例:**

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

**题解**

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. 二叉树的最近公共祖先][236.] ####

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

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

[百度百科][Link 1]中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（**一个节点也可以是它自己的祖先**）。”

**示例 1：**

![在这里插入图片描述][20210210230657799.png]

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

**示例 2：**

![在这里插入图片描述][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

**题解**

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;
        }
    }

[235.]: https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
[Link 1]: https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fr=aladdin
[20210210230729177.png]: /images/20221024/025af5d0008145c5a28968d7dd63f7de.png
[450.]: https://leetcode-cn.com/problems/delete-node-in-a-bst/
[108.]: https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
[236.]: https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
[20210210230657799.png]: /images/20221024/b9f48e6fc36e4516b1b62e39a93a3a1d.png
[20210210230712731.png]: /images/20221024/1e0f77a1a2a84a11b6a6843ca1bdee82.png