分治法在二叉树的应用

二叉树

每个节点最多有两个子树的树结构。

二叉树的高度：

O(logN)~O(N)之间

二叉树的时间复杂度：

时间复杂度：O(一次的复杂度)*次数 空间复杂度：O(一次的复杂度+深度)

分治法

将问题分解为子问题求解，自己将子问题的结果进行合并，求出最终解。

二叉树中分治法的应用：

在二叉树中，考虑整棵树在该问题上的结果和左右子树在该问题上的结果之间的关系。

第一类：二叉树上的求值，求路径

最小子树

路径总和 II

求根节点到叶节点数字之和

二叉搜索树的最近公共祖先I

最近公共祖先 III

第二类：二叉树结构变化

二叉树展开为链表

第三类：二叉查找树(Binary Search Tree)

    左子树的值小于根节点的值，右子树的值大于根节点的值。

二叉搜索树的第k大节点

二叉搜索树中最接近的值

二叉搜索树中最接近的值 II

二叉平衡树(Balanced Binary Tree)：

1.可以是一颗空树 2.左右子树的高度之差不大于1 3.子树也是一颗二叉平衡树

红黑树(Balanced BST)

Java中的TreeMap和TreeSet的数据结构就使用了红黑树

Java1.8中的HashMap的实现使用了TreeMap和LinkedList，使得在键冲突时快速查找键值。

效率：

O(logN)时间内实现增删改查 O(logN)时间内实现找最大最小值 

推荐这些技术文章：

java二叉树--二叉查找树

一、二叉查找树

每个结点都含有一个Comparable的键（以及相关的值），每个结点的键都大于左子树中的任意结点的键而小于右子树的任意结点的键
每个节点都含有一个键，一个值，一条左链接和一条右链接，一个节点计数器。左链接指向一棵小于该节点的所有键组成的二叉查找树，右链接指向一颗由大于该节点的所有键组成的二叉查找树。
查找：从根节点开始，在每个结点中查找的进程都会递归的在他的一个子节点展开，对于...

669. 修剪二叉搜索树

深度优先搜索
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {

if (root == null){
return root;
}

/**
* 如果根节点小于最小值，那其左子树肯定也小于最小值...

数据结构-二叉树

​
树
树是一种非常重要的非线性数据结构。
树的树形图表示法规定在用直线连接起来的两端结点中，处在上端的结点是前驱，处在下端的结点是后继。
树的逻辑结构可表示为T=(D,R);
数据元素集合：D={A,B,C,D,E,F,G,H,I,J,K,L}
各数据元素之间的前后关系：R = {<A,B>,<A,C>,<A,D>,<B,E>,<B,F&g...

700. 二叉搜索树中的搜索

深度优先搜索
class Solution {
public TreeNode searchBST(TreeNode root, int val) {

if (root == null){
return root;
}

if (root.val == val){
retur...