LeetCode——树：BST

分手后的思念是犯贱 2023-07-12 14:38 53阅读 0赞

# BST #

--------------------

## 目录 ##

1.  概述
2.  修剪二叉查找树（LeetCode669）
3.  寻找二叉查找树的第k个元素（LeetCode230）
4.  把二叉查找树每个节点的值都加上比它大的节点的值
5.  二叉查找树的最近公共祖先（LeetCode235）
6.  二叉树的最近公共祖先（LeetCode236）
7.  从有序数组中构建二叉查找树（LeetCode108）
8.  根据有序链表构建平衡的二叉查找树（LeetCode109）
9.  在二叉查找树中寻找两个节点，使它们的和为一个给定值（LeetCode653）
10. 在二叉查找树中查找两个节点之差的最小绝对值（LeetCode530）

--------------------

### 0. 概述 ###

1. 二叉查找树（BST）：根节点大于左子树所有节点，小于等于右子树所有节点
    	2. 二叉查找树中序遍历有序

--------------------

### 1. 修剪二叉查找树（LeetCode669） ###

1.  概述
    
    1.  给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在\[L, R\]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。  
        ![在这里插入图片描述][20200310100429654.png]
2.  思路
    
    1.  由二叉树的性质可知，如果root.val大于R，说明root的右边节点全都大于R，所有可以直接跳到它的root.left继续遍历。
    2.  同理如果root.val小于L，说明它的左边节点全部小于L，所有直接跳到它的右节点继续遍历
    3.  如果符合，则递归到下一个节点，构建新的二叉树节点  
        root.left = trim(root.left, L, R)  
        root.right = trim(root.right, L, R)
3.  代码

public static TreeNode trimBST(TreeNode root, int L, int R) {
            if (root == null)
                return null;
            if (root.val > R) {
                return trimBST(root.left, L, R);
            }
            if (root.val < L) {
                return trimBST(root.right, L, R);
            }
            root.left = trimBST(root.left, L, R);
            root.right = trimBST(root.right, L, R);
            return root;
        }

--------------------

### 2. 寻找二叉查找树的第k个元素（LeetCode230） ###

1.  概述
    
    1.  给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。  
        ![在这里插入图片描述][20200310100844507.png]
2.  思路
    
    1.  利用中序遍历，遍历的结果就是有序的，返回第k个结果即可
3.  代码

static int cnt = 0;
        static int val;
    
        public static int kthSmallest(TreeNode root, int k) {
            inOrder(root, k);
            return val;
        }
    
        private static void inOrder(TreeNode root, int k) {
            if (root == null)
                return;
            inOrder(root.left, k);
            cnt++;
            if (k == cnt) {
                val = root.val;
                return;
            }
            inOrder(root.right, k);
        }

--------------------

### 3. 把二叉查找树每个节点的值都加上比它大的节点的值 ###

1.  概述  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]
2.  思路  
    1. 按照节点值降序遍历所有节点，同时记录已经遍历过的节点值的和，并把这个和加到当前节点的值中。这种遍历树的方法被称作反序中序遍历。  
    2. 具体就是先遍历右子树，然后记录遍历过的值的和，加到当前节点的值中
3.  代码

private static int sum = 0;
    
        public static TreeNode convertBST(TreeNode root) {
            traver(root);
            return root;
        }
    
        private static void traver(TreeNode node) {
            if (node == null)
                return;
            traver(node.right);
            sum += node.val;
            node.val = sum;
            traver(node.left);
        }

--------------------

### 4. 二叉查找树的最近公共祖先（LeetCode235） ###

1.  概述
    
    1.  给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]
2.  思路
    
    1.  利用二叉查找树性质，如果当前节点root.val>p.val&&root.val>q.val，那么要找的公共节点就在左子树上
    2.  如果root.val<p.val&&roo.val<q.val，那么要找的节点就在右子树上
    3.  否则找到公共节点返回即可
3.  代码

public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            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;
        }

--------------------

### 5. 二叉树的最近公共祖先（LeetCode236） ###

1.  概述
    
    1.  给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]
2.  思路
    
    1.  利用递归，从下往上判断，如当前节点是5，则判断它的左边节点有没有等于p，q的节点，判断它的右边节点有没有等于p，q的节点  
        1. 如果left和right不为null，则说明找到公共节点，返回root  
        2. 如果left不为null，right为null，说明找到一边的节点，返回left  
        3. 如果left为null，返回right
3.  代码

public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || root == p || root == q) {
                return root;
            }
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            return left == null ? right : right == null ? left : root;
        }

--------------------

### 6. 从有序数组中构建二叉查找树（LeetCode108） ###

1.  概述
    
    1.  将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 3]
2.  思路
    
    1.  从中间元素开始创建二叉查找树  
        1. 获取中间元素下标int mIdx=(sIdx+eIdx)/2  
        2. 创建根节点TreeNode root = new TreeNode(nums\[mIdx\])  
        3. 递归创建左右节点  
        root.left = toBST(nums, sIdx, mIdx-1)  
        root.right = toBST(nums, mIdx+1, eIdx)  
        4. 最后返回root即可
3.  代码

public static TreeNode sortedArrayToBST(int[] nums) {
            return toBST(nums, 0, nums.length - 1);
        }
    
        private static TreeNode toBST(int[] nums, int sIdx, int eIdx) {
            if (sIdx > eIdx)
                return null;
            int mid = (sIdx + eIdx) / 2;
            TreeNode root = new TreeNode(nums[mid]);
            root.left = toBST(nums, sIdx, mid - 1);
            root.right = toBST(nums, mid + 1, eIdx);
            return root;
        }

--------------------

### 7. 根据有序链表构建平衡的二叉查找树（LeetCode109） ###

1.  概述
    
    1.  给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。  
        ![在这里插入图片描述][20200310104939828.png]
2.  思路
    
    1.  给定列表中的中间元素将会作为二叉搜索树的根，该点左侧的所有元素递归的去构建左子树，同理右侧的元素构建右子树。这样能保证最后构建出的二叉搜索树是平衡的
    2.  关键的找到中间元素  
        1. 利用快慢指针，慢指针每次走一步，快指针每次走两步，当fast指针为null，或者fast.next指针为null时，pre.next就是中间元素
    3.  找到中间节点后，将中间节点mid的前一个节点preMid.next=null，断开。然后创建新节点new TreeNode(mid.val)
    4.  node的左节点为从head开始的链表继续递归。node的右节点为mid.next元素开始的链表继续递归
3.  代码

public static TreeNode sortedListToBST(ListNode head) {
            if (head == null)
                return null;
            if (head.next == null)
                return new TreeNode(head.val);
            ListNode preMid = preMid(head);
            ListNode mid = preMid.next;
            preMid.next = null;
            TreeNode t = new TreeNode(mid.val);
            t.left = sortedListToBST(head);
            t.right = sortedListToBST(mid.next);
            return t;
        }
    
        private static ListNode preMid(ListNode head) {
            ListNode slow = head;
            ListNode fast = head.next;
            ListNode pre = head;
            while (fast != null && fast.next != null) {
                pre = slow;
                slow = slow.next;
                fast = fast.next.next;
            }
            return pre;
        }

--------------------

### 8. 在二叉查找树中寻找两个节点，使它们的和为一个给定值（LeetCode653） ###

1.  概述
    
    1.  给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。  
        ![在这里插入图片描述][20200310105141354.png]
2.  思路
    
    1.  利用HashSet，在遍历过程中，将元素放入set中。对于每个值为p的节点，在set中检查是否存在k-p。如果存在，那么在该树上就能找到两个节点的和为k；否则，将p放入set中
    2.  如果遍历完整棵树都没有找到一对节点和为k，那么该树上不存在两个和为k的节点
3.  代码

public boolean findTarget(TreeNode root, int k){
            Set<Integer> set = new HashSet<>();
            return find(root,k,set);
        }
    
        private boolean find(TreeNode root, int k, Set<Integer> set) {
            if (root==null)
                return false;
            if (set.contains(k-root.val))
                return true;
            set.add(root.val);
            return find(root.left,k,set)||find(root.right,k,set);
        }

--------------------

### 9. 在二叉查找树中查找两个节点之差的最小绝对值（LeetCode530） ###

1.  概述
    
    1.  给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 4]
2.  思路  
    1. 要求任意两节点绝对值最小，根据二叉搜索树中序遍历结果有序，则是计算前后两个节点的差，从中选择最小的差值即可
3.  代码

private int minDiff = Integer.MAX_VALUE;
        private TreeNode preNode = null;
    
        public int getMinimumDifference(TreeNode root) {
            inOrder(root);
            return minDiff;
        }
    
        private void inOrder(TreeNode node) {
            if (node == null)
                return;
            inOrder(node.left);
            if (preNode != null)
                minDiff = Math.min(minDiff, node.val - preNode.val);
            preNode = node;
            inOrder(node.right);
        }

[20200310100429654.png]: https://img-blog.csdnimg.cn/20200310100429654.png
[20200310100844507.png]: https://img-blog.csdnimg.cn/20200310100844507.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200310100926492.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200310104015863.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200310104322409.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200310104715997.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[20200310104939828.png]: https://img-blog.csdnimg.cn/20200310104939828.png
[20200310105141354.png]: https://img-blog.csdnimg.cn/20200310105141354.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200310105334827.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70