7. LintCode 分治题目（一）

LintCode 597：具有最大平均数的子树

https://www.lintcode.com/problem/subtree-with-maximum-average

描述

给一棵二叉树，找到有最大平均值的子树。返回子树的根结点。
LintCode会打印出根结点为你返回节点的子树，保证有最大平均数子树只有一棵

样例

  1. 输入：
  2. {1,-5,11,1,2,4,-2}
  3. 输出：11
  4. 说明:
  5. 这棵树如下所示：
  6.      1
  7.    /   \
  8.  -5     11
  9.  / \   /  \
  10. 1   2 4    -2 
  11. 11子树的平均值是4.333，为最大的。
  13. 输入：
  14. {1,-5,11}
  15. 输出：11
  16. 说明:
  17.      1
  18.    /   \
  19.  -5     11
  20. 1,-5,11 三棵子树的平均值分别是 2.333,-5,11。因此11才是最大的

解题思路

和最小子树思路差不多，对一棵子树而言：最大平均值要么是它本身，要么在左子树中或者右子树中。

AC代码

  1. public class Solution {
  2.     // 记录答案
  3.     TreeNode ans;
  4.     // 初始化一个非常小的值
  5.     double ave = Integer.MIN_VALUE;
  7.     public TreeNode findSubtree2(TreeNode root) {
  8.         if (root == null) {  return null;  }
  9.         // 遍历树
  10.         findTree(root);
  11.         return ans;
  12.     }
  14.     // 计算以root为根的子树的平均值
  15.     private Info findTree(TreeNode root) {
  16.         int count = 1;
  17.         int add = root.val;
  18.         // 查找左子树
  19.         if (root.left != null) {
  20.             Info left = findTree(root.left);
  21.             count += left.count;
  22.             add += left.add;
  23.         }
  24.         // 查找右子树
  25.         if (root.right != null) {
  26.             Info right = findTree(root.right);
  27.             count += right.count;
  28.             add += right.add;
  29.         }
  30.         // 计算当前子树的平均值，更新答案
  31.         double x = (double) add / count;
  32.         if (x > ave) {
  33.             ans = root;
  34.             ave = x;
  35.         }
  36.         return new Info(count, add);
  37.     }
  38. }
  39. // 想要知道返回值，需要两个信息，子树的节点个数和子树节点值的和
  40. class Info {
  41.     int count;
  42.     int add;
  44.     Info(int count, int add) {
  45.         this.add = add;
  46.         this.count = count;
  47.     }
  48. }

LintCode 174：翻转二叉树

https://www.lintcode.com/problem/invert-binary-tree

描述

翻转一棵二叉树。左右子树交换。

样例

  1. 输入: {1,3,#}
  2. 输出: {1,#,3}
  3. 解释:
  4.       1    1
  5.      /  =>  \
  6.     3        3
  8. 输入: {1,2,3,#,#,4}
  9. 输出: {1,3,2,#,4}
  10. 解释: 
  12.       1         1
  13.      / \       / \
  14.     2   3  => 3   2
  15.        /       \
  16.       4         4

解题思路

对一个节点：

  • 交换它的左右子树
  • 递归交换左右子树

这样整棵树都进行了翻转

AC代码

  1. public void invertBinaryTree(TreeNode root) {
  2.     if (root == null) {
  3.         return;
  4.     }
  5.     // 交换左右子树
  6.     TreeNode tmp = root.left;
  7.     root.left = root.right;
  8.     root.right = tmp;
  9.     // 递归交换左右子树
  10.     invertBinaryTree(root.left);
  11.     invertBinaryTree(root.right);
  12. }

LintCode 95：验证二叉搜索树

https://www.lintcode.com/problem/validate-binary-search-tree

描述

给定一个二叉树，判断它是否是合法的二叉查找树(BST)
一棵BST定义为：

  • 节点的左子树中的值要严格小于该节点的值。
  • 节点的右子树中的值要严格大于该节点的值。
  • 左右子树也必须是二叉查找树。
  • 一个节点的树也是二叉查找树。

    样例

    ```java 输入：{-1} 输出：true 解释： 二叉树如下(仅有一个节点）: -1 这是二叉查找树。

输入：{2,1,4,#,#,3,5} 输出：true 解释： 二叉树如下： 2 / \ 1 4 / \ 3 5 这是二叉查找树。

  1. <a name="I0mkM"></a>
  2. #### 解题思路
  3. 两个思路：
  5. - 从下往上：对于一个节点，找出它左子树的最大值，应该小于它；找出它右子树的最小值，应该大于它
  6. - 从下往上：对于一棵左子树，它所有的值应该小于父亲，对于一棵右子树，它所有的值应该大于父亲，所以每个节点都有一个取值范围，满足这个范围便是二叉搜索树
  7. <a name="FiKwd"></a>
  8. #### AC代码
  9. ```java
  10. public boolean isValidBST(TreeNode root) {
  11.     return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
  12. }
  14. public boolean isValid(TreeNode root, long minValue, long maxValue) {
  15.     if (root == null) {
  16.         return true;
  17.     }
  18.     if (root.val <= minValue || root.val >= maxValue) {
  19.         return false;
  20.     }
  21.     // 左子树的最大值应该小于该节点，右子树的最小值应该大于该节点
  22.     return isValid(root.left, minValue, root.val) && isValid(root.right, root.val, maxValue);
  23. }

LintCode 11：二叉查找树搜索区间

https://www.lintcode.com/problem/search-range-in-binary-search-tree

描述

给定一个二叉查找树和范围[k1, k2]。按照升序返回给定范围内的节点值。

样例

  1. 输入：{5},6,10
  2. 输出：[]
  3.         5
  4. 它将被序列化为 {5}
  5. 没有数字介于6和10之间
  7. 输入：{20,8,22,4,12},10,22
  8. 输出：[12,20,22]
  9. 解释：
  10.         20
  11.        /  \
  12.       8   22
  13.      / \
  14.     4   12
  15. 它将被序列化为 {20,8,22,4,12}
  16. [12,20,22]介于10和22之间

解题思路

按中序遍历走，在区间内的加入答案。可以剪枝优化。

AC代码

  1. public class Solution {
  3.     List<Integer> ans = new ArrayList<>();
  5.     public List<Integer> searchRange(TreeNode root, int k1, int k2) {        
  6.         search(root, k1, k2);
  7.         return ans;
  8.     }
  10.     private void search(TreeNode root, int k1, int k2) {
  11.         if (root == null) {
  12.             return;
  13.         }
  14.         // 先搜寻左子树，再搜寻右子树，这样能保持有序
  15.         search(root.left, k1, k2);
  16.         if (root.val >= k1 && root.val <= k2) {
  17.             ans.add(root.val);
  18.         }
  19.         search(root.right, k1, k2);
  20.     }
  21. }

LintCode 901：二叉搜索树中最接近的值 II关注问题

https://www.lintcode.com/problem/closest-binary-search-tree-value-ii

描述

给定一棵非空二叉搜索树以及一个target值，找到 BST 中最接近给定值的 k 个数。

  • 给出的target值为浮点数
  • 你可以假设 k 总是合理的，即 k ≤ 总节点数
  • 我们可以保证给出的 BST 中只有唯一一个最接近给定值的 k 个值的集合

    样例

    ```java 输入: {1} 0.000000 1 输出: [1] 解释： 二叉树 {1}，表示如下的树结构： 1

输入: {3,1,4,#,2} 0.275000 2 输出: [1,2] 解释： 二叉树 {3,1,4,#,2}，表示如下的树结构： 3 / \ 1 4 \ 2 

  1. <a name="kawvt"></a>
  2. #### 解题思路
  4. 1. 二分法篇章中做过一道在排序数组中找最接近的k个数[https://www.lintcode.com/problem/find-k-closest-elements](https://www.lintcode.com/problem/find-k-closest-elements)，所以可以先将搜索树中序遍历转换为数组，然后采用该题解法。
  5. 1. 还是中序遍历，但是不转化成数组了。直接在遍历的过程中查找K个数，维护一个队列，队列最多K个数，为最接近target的k的数，中序遍历树，然后维护队列，队头是离target最远的数，队列不足k个数时，当前节点值直接加入队列，如果超过k个数，当前节点比队头更接近target时，取出，队头，当前节点加入队尾，队列有K个数，并且当前节点距离target比队首更远，表示已经找到了最接近的k个数（剪枝优化）
  6. <a name="EpHBF"></a>
  7. #### AC代码
  8. ```java
  9. public class Solution {
  10.     // 存储k个接近target的数的队列
  11.     Deque<Integer> deque = new ArrayDeque<>();
  13.     public List<Integer> closestKValues(TreeNode root, double target, int k) {
  14.         // 中序遍历
  15.         order(root, target, k);
  16.         List<Integer> list = new ArrayList<>(deque);
  17.         return list;
  18.     }
  20.     private void order(TreeNode root, double target, int k) {
  21.         if (root == null) { return; }
  22.         // 中序遍历，保证队首是最远离target的数
  23.         order(root.left, target, k);      
  24.         if (deque.size() < k) {
  25.             // 队列不足k个数，当前节点直接加入队列
  26.             deque.add(root.val);
  27.         } else {            
  28.             if (Math.abs(deque.peek() - target) > Math.abs(root.val - target)) {
  29.                 // 当前节点比队首更接近target，淘汰队首
  30.                 deque.removeFirst();
  31.                 deque.add(root.val);
  32.             } else {
  33.                 // 队首已经比当前节点更接近target了，按照中序遍历，后面的节点只会更加远离target，所以剪枝优化
  34.                 return;
  35.             } 
  36.         }
  37.         // 中序遍历
  38.         order(root.right, target, k);
  39.     }
  40. }

LintCode 87：删除二叉查找树的节点

https://www.lintcode.com/problem/remove-node-in-binary-search-tree

描述

给定一棵具有不同节点值的二叉查找树，删除树中与给定值相同的节点。如果树中没有相同值的节点，就不做任何处理。你应该保证处理之后的树仍是二叉查找树。

样例

  1. 输入: 
  2. Tree = {5,3,6,2,4}
  3. k = 3
  4. 输出: {5,2,6,#,4} 或 {5,4,6,2}
  5. 说明:
  6. 给定了以下二叉搜索树:
  7.     5
  8.    / \
  9.   3   6
  10.  / \
  11. 2   4
  12. 移去3，你可以返回:
  13.     5
  14.    / \
  15.   2   6
  16.    \
  17.     4
  18. 或
  19.     5
  20.    / \
  21.   4   6
  22.  /
  23. 2
  25. 输入: 
  26. Tree = {5,3,6,2,4}
  27. k = 4
  28. 输出: {5,3,6,2}
  29. 说明:
  30. 给定了以下二叉搜索树:
  31.     5
  32.    / \
  33.   3   6
  34.  / \
  35. 2   4
  36. 移去4，你应该返回
  37.     5
  38.    / \
  39.   3   6
  40.  /
  41. 2

解题思路

删除一个节点，有4种情况：

  • 该节点是叶子节点：直接删除
  • 该节点只有左儿子：将左儿子与父亲节点连接即可
  • 该节点只有右儿子：将右儿子与父亲节点连接即可
  • 左右儿子都有
    • 从左子树中选出最大的，删掉它，把节点值设为该最大值。
    • 从右儿子中选出最小的，删掉它，把节点值设为该最小值。

4种情况简化一下：

  • 没有右儿子：将左儿子与父亲节点连接即可
  • 有右儿子：找到右儿子中最小的节点，删掉，把节点设为该最小值

    AC代码

    ```java public TreeNode removeNode(TreeNode root, int value) { // 因为root有可能也是删除的点，所以建个哨兵节点，降低代码复杂度，这样删除root的情况不用特殊处理 TreeNode sb = new TreeNode(0); sb.left = root; // 中序遍历找到要删除节点的父亲。 TreeNode father = find(root, value, sb); // 删除节点（没有则不用删除） if (father.left != null && father.left.val == value) {
    1.   delete(father, father.left);
    } else if (father.right != null && father.right.val == value) {
    1.   delete(father, father.right);
    } // 返回数的根节点 return sb.left; }

public TreeNode find(TreeNode root, int value, TreeNode father) { if (root == null) { return father; } if (root.val == value) { return father; } if (root.val < value) { return find(root.right, value, root); } return find(root.left, value, root); }

// 删除 p 的儿子 node，并保持二叉搜索树 public void delete(TreeNode p, TreeNode node) { if (node.right == null) { if (p.left == node) { p.left = node.left; } else { p.right = node.right; } } else { TreeNode tmp = node.right; TreeNode right = node; // 找到右子树中最小的节点 while (tmp.left != null) { right = tmp; tmp= tmp.left; } // 将最小节点与当前节点替换 if (right.right == tmp) { right.right = tmp.right; } else { right.left = tmp.right; } // 从树中删除当前节点 if (p.left == node) { p.left = tmp; } else { p.right = tmp; } // 最小节点接收删除节点的左右儿子 tmp.left = node.left; tmp.right = node.right; }

} ```