当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直到可以直接求出解为止。这就是分治策略的基本思想。

LintCode 900：二叉搜索树中最接近的值

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

描述

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

  • 给出的目标值为浮点数
  • 我们可以保证只有唯一一个最接近给定值的节点

    样例

    ```java 输入: root = {5,4,9,2,#,8,10} and target = 6.124780 输出: 5 解释： 二叉树 {5,4,9,2,#,8,10}，表示如下的树结构：
    1.   5
    2.  / \
    4 9 / / \ 2 8 10

输入: root = {3,2,4,1} and target = 4.142857 输出: 4 解释： 二叉树 {3,2,4,1}，表示如下的树结构： 3 / \ 2 4 / 1 

  1. <a name="QdVFu"></a>
  2. #### 解题思路
  3. 对一个节点，找最接近的值有三个：
  5. - 节点本身与target的差值
  6. - 节点左子树与target的最小差值
  7. - 节点右子树与target的最小差值
  9. 在这三个值中选出最小的那个节点，返回val值。
  11. <a name="KESf0"></a>
  12. #### AC代码
  13. ```java
  14. public int closestValue(TreeNode root, double target) {
  15.     // 节点本身与target的差值
  16.     double diff = differ(root.val, target);
  17.     int re = root.val;
  19.     if (root.left != null) {
  20.         int left = closestValue(root.left, target);
  21.         // 左子树与target的差值
  22.         double leftDiff = differ(left, target);
  23.         if (diff > leftDiff) {
  24.             diff = leftDiff;
  25.             // 左子树更接近target，返回左子树中最接近target的节点值
  26.             re = left;
  27.         }
  28.     }
  30.     if (root.right != null) {
  31.         int right = closestValue(root.right, target);
  32.         // 右子树与target的差值
  33.         double rightDiff = differ(right, target);
  34.         if (diff > rightDiff) {
  35.             // 右子树更进阶target，返回右子树中最接近target的节点值
  36.             re = right;
  37.         }
  38.     }
  39.     // 返回以该节点为跟的子树中与target最接近的节点值
  40.     return re;
  41. }
  43. // 返回两个数相减的绝对值
  44. public double differ(int val, double target) {
  45.     double x = val - target;
  46.     return x < 0 ? x * -1 : x;
  47. }

LintCode 596：最小子树

https://www.lintcode.com/problem/minimum-subtree

描述

给一棵二叉树, 找到和为最小的子树, 返回其根节点。输入输出数据范围都在int内。
LintCode会打印根节点为你返回节点的子树。保证只有一棵和最小的子树并且给出的二叉树不是一棵空树。

样例

  1. 输入:
  2. {1,-5,2,1,2,-4,-5}
  3. 输出:1
  4. 说明
  5. 这棵树如下所示：
  6.      1
  7.    /   \
  8.  -5     2
  9.  / \   /  \
  10. 1   2 -4  -5 
  11. 整颗树的和是最小的，所以返回根节点1.
  13. 输入:
  14. {1}
  15. 输出:1
  16. 说明:
  17. 这棵树如下所示：
  18.    1
  19. 这棵树只有整体这一个子树，所以返回1.

解题思路

对于一个节点：

  • 左子树的和
  • 右子树的和
  • 左子树的和加上右子树的和加上自己的值

选出三个中最小的和便可找到最下子树。

AC代码

  1. public class Solution {
  2.     // 记录答案
  3.     TreeNode minRoot;
  4.     int min = Integer.MAX_VALUE;
  6.     public TreeNode findSubtree(TreeNode root) {
  7.         // write your code here
  8.         addTree(root);
  9.         return minRoot;
  10.     }
  11.     // 查找该子树的和
  12.     public int addTree(TreeNode root) {
  13.         int count = root.val;
  14.         if (root.left != null) {
  15.             // 加上左子树
  16.             count += addTree(root.left);
  17.         }
  18.         if (root.right != null) {
  19.             // 加上右子树
  20.             count += addTree(root.right);
  21.         }
  22.         if (min > count) {
  23.             // 更新答案
  24.             min = count;
  25.             minRoot = root;
  26.         }
  27.         // 返回该节点为根的子树和
  28.         return count;
  29.     }
  30. }

LintCode 453：将二叉树拆成链表

https://www.lintcode.com/problem/flatten-binary-tree-to-linked-list

描述

将一棵二叉树按照前序遍历拆解成为一个 假链表。所谓的假链表是说，用二叉树的 right 指针，来表示链表中的 next 指针。
不要忘记将左儿子标记为 null，否则你可能会得到空间溢出或是时间溢出。

样例

  1. 输入：{1,2,5,3,4,#,6}
  2. 输出：{1,#,2,#,3,#,4,#,5,#,6}
  3. 解释：
  4.      1
  5.     / \
  6.    2   5
  7.   / \   \
  8.  3   4   6
  10. 1
  11. \
  12.  2
  13.   \
  14.    3
  15.     \
  16.      4
  17.       \
  18.        5
  19.         \
  20.          6
  22. 输入：{1}
  23. 输出：{1}
  24. 解释：
  25.          1
  26.          1

解题思路

前序遍历：根左右
对一个节点，要按前序遍历成链，那么要把左儿子变成有右儿子，然后把左儿子子树的最后一个的右儿子连接至自己先前的右儿子，然后返回右儿子子树成链后的最后一个节点。
所以需要一个函数找到当前节点子树成链后的最后一个节点，对一个节点，有四种情况：

  • 没有左右儿子：节点本身就是链的最后一个，返回节点
  • 只有左儿子：把右儿子设为左儿子，左儿子置空，返回左儿子成链后的最后一个节点
  • 只有右儿子：返回右儿子成链后的最后一个节点
  • 左右儿子都有：首先找到左右儿子成链后的最后一个节点，然后把左儿子成链后的最后一个节点的右儿子置为当前节点的右儿子，然后把当前节点的右儿子置为当前节点的左儿子，然后返回之前找到的右儿子成链后的最后一个节点。

    AC代码

    ```java public void flatten(TreeNode root) { if (root != null) {
    1.   chain(root);
    } }

// 成链函数，返回当前节点子树成链后的最后一个节点 private TreeNode chain(TreeNode root) { if (root.left == null && root.right == null) { // 没有左右儿子，返回本身 return root; } if (root.left == null) { // 只有右儿子，直接返回右儿子成链后的最后一个节点 return chain(root.right); } if (root.right == null) { // 只有左儿子，把左儿子接到右儿子上，然后置空左儿子，返回右儿子成链后的最后一个节点 root.right = root.left; root.left = null; return chain(root.right); } // 左右儿子都有 TreeNode left = root.left; // 找到左儿子成链后的最后一个节点，将其右儿子接入当前节点的右儿 TreeNode next = chain(left); TreeNode right = root.right; // 右儿子置为左儿子，左儿子置空 root.right = left; root.left = null; next.right = right; // 返回成链后的最后一个节点 return chain(right);

}

  1. <a name="HkkNf"></a>
  2. ### LintCode 902：BST中第K小的元素
  3. [https://www.lintcode.com/problem/kth-smallest-element-in-a-bst](https://www.lintcode.com/problem/kth-smallest-element-in-a-bst)
  4. <a name="8mhP3"></a>
  5. #### 描述
  6. 给一棵二叉搜索树，写一个 `KthSmallest` 函数来找到其中第 K 小的元素。<br />你可以假设 k 总是有效的， `1 ≤ k ≤ 树的总节点数`。
  7. <a name="kup5j"></a>
  8. #### 样例
  9. ```java
  10. 输入：{1,#,2},2
  11. 输出：2
  12. 解释：
  13.     1
  14.      \
  15.       2
  16. 第二小的元素是2。
  18. 输入：{2,1,3},1
  19. 输出：1
  20. 解释：
  21.   2
  22.  / \
  23. 1   3
  24. 第一小的元素是1。

解题思路

  1. 二叉搜索树中序遍历后是一个有序数组，数组的第K位即为第K小的元素，所以中序遍历走k - 1次便是第K小元素
  2. 对二叉搜索树的一个节点，它左子树所有节点都比它小，右子树都比它大，所以如果我们知道了左子树和右子树的节点个数，我们就能知道第K小的元素在哪里
  • 左子树的节点个数 t = k - 1，那么当前节点就是第 k 小元素
  • 左子树的节点个数 t >= k，第k小元素在左子树中

  • 左子树的节点个数 t < k，第 k 小元素在右子树中，并且是右子树中的 第（k - t - 1）小元素

    AC代码

    1. public class Solution {
    3.   Map<TreeNode, Integer> map = new HashMap<>();
    5.   public int kthSmallest(TreeNode root, int k) {
    6.       // 计算每个节点为根的子树的节点个数
    7.       count(root);
    8.       // 寻找第k小元素
    9.       return findK(root, k).val;
    10.   }
    12.   private TreeNode findK(TreeNode root, int k) {
    13.       int add = root.left != null ? map.get(root.left) : 0;
    14.       if (add == k - 1) {
    15.           // 左子树的节点个数 t =  k - 1，那么当前节点就是第 k 小元素
    16.           return root;
    17.       }
    18.       if (add >= k) {
    19.           // 左子树的节点个数 t >= k，第k小元素在左子树中
    20.           return findK(root.left, k);
    21.       }
    22.       // 左子树的节点个数 t  <  k，第 k 小元素在右子树中，并且是右子树中的 第（k - t - 1）小元素
    23.       return findK(root.right, k - add - 1);
    24.   }
    26.   // 记录每个节点为根的子树的节点数目
    27.   public int count(TreeNode root) {
    28.       int add = 1;
    29.       if (root.left != null) {
    30.           add += count(root.left);
    31.       }
    32.       if (root.right != null) {
    33.           add += count(root.right);
    34.       }
    35.       map.put(root, add);
    36.       return add;
    37.   }
    38. }

    LIntCode 88：最近公共祖先

    https://www.lintcode.com/problem/lowest-common-ancestor-of-a-binary-tree

    描述

    给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。
    最近公共祖先是两个节点的公共的祖先节点且具有最大深度。
    假设给出的两个节点都在树中存在

    样例

    ```java 输入：{1},1,1 输出：1 解释： 二叉树如下（只有一个节点）:

    1.    1

    LCA(1,1) = 1

输入：{4,3,7,#,#,5,6},3,5 输出：4 解释： 二叉树如下:

  1.   4
  2.  / \
  3. 3   7
  4.    / \
  5.   5   6

LCA(3, 5) = 4 

  1. <a name="zkGeB"></a>
  2. #### 解题思路
  3. 从根节点开始查找：<br />对于一个节点：
  5. - 若该节点的值是两个节点之一，其左右子树中有另一个节点，则该节点为最近公共祖先
  6. - 若该节点的左子树中含有两个节点，则最近公共祖先在左子树中
  7. - 若该节点的右子树中含有两个节点，则最近公共祖先在右子树中
  8. - 若该节点的左右子树分别包含一个节点，则该节点为最近公共祖先
  9. <a name="217IC"></a>
  10. #### AC代码
  11. ```java
  12. public class Solution {
  13.     // 记录答案
  14.     TreeNode ans;
  16.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
  17.         if (A.val == B.val) {
  18.             // A，B相同直接返回
  19.             return A;
  20.         }
  21.         // 查找答案
  22.         isContainAB(root, A, B);
  23.         return ans;
  24.     }
  26.     public boolean isContainAB(TreeNode root, TreeNode a, TreeNode b) {
  27.         if (root == null) {
  28.             return false;
  29.         }
  30.         // 左儿子中是否含有 A 或 B
  31.         boolean lson = isContainAB(root.left, a, b);
  32.         // 右儿子中是否含有 A 或 B
  33.         boolean rson = isContainAB(root.right, a, b);
  34.         // 左儿子和右儿子分别含有一个节点， 或者该节点是A，B之一，左右子树中含有另一个节点，则该点为最近公共祖先
  35.         if ((lson && rson) || ((root.val == a.val || root.val == b.val) && (lson || rson))) {
  36.             ans = root;
  37.         }
  38.         // 返回该节点为根的子树是否含有 A 或 B
  39.         return lson || rson || root.val == a.val || root.val == b.val;
  41.     }
  42. }