算法分析 [树] 2019-02-25

1 树基本理解

1.1 基础

104. 树最大深度 Maximum Depth of Binary Tree easy
法1. 时间复杂度O(n) 空间复杂度O(1)
从叶子节点的null返回0，逐级向上取最大值+1

111. 数最小深度 Minimum Depth of Binary Tree easy
法1. 时间复杂度O(n) 空间复杂度O(1)
从叶子节点的null返回0，逐级向上取，如果一边节点返回为0，最用另一边值+1，如果两边都有值，取最小值+1

107. 二叉树层次遍历反转 Binary Tree Level Order Traversal II easy
法1. 时间复杂度O(n) 空间复杂度O(m)
使用LinkedList.addFirst()
637. 二叉树层次遍历求每层次平均数 Average of Levels in Binary Tree easy
法1. 时间复杂度O(n) 空间复杂度O(m)
每层级加法后求除法

513. 查找树左下角的节点值 Find Bottom Left Tree Value easy
法1. 时间复杂度O(n) 空间复杂度O(2)
使用BFS，从右往左走，但是不是标准的层次遍历，是不断的找右边节点，因此最后一个几点就是左底层树

110.平衡二叉树 Balanced Binary Tree easy
法1. 时间复杂度O(n) 空间复杂度O(1)
从叶子节点的null返回0，逐级向上取，如果left和right的差值查过了1，说明不平衡，设置全局变量为false，如果已经是false则继续向上，但是已经说明不平衡了
法2. 时间复杂度O(n) 空间复杂度O(1)

700. 二叉搜索树查找 Search in a Binary Search Tree easy
法1. 时间复杂度O(n) 空间复杂度O(logn)
使用BFS 广度遍历（层次遍历），逐个查找
法2. 时间复杂度O(logn) 空间复杂度O(1)
使用折半查找，当node.val>val向node.left，否则node.right

108. 转换有序数组为二叉查找树 Convert Sorted Array to Binary Search Tree easy
法1. 时间复杂度O(logn) 空间复杂度O(n)
使用分治法，折半为left、right

1.2 强化

226. 二叉树对称反转 Invert Binary Tree easy
法1. 时间复杂度O(m) 空间复杂度O(1)
每次交换left 和 right，遍历向下

669. 按范围裁剪二叉树 Trim a Binary Search Tree easy
法1. 时间复杂度O(m) 空间复杂度O(1)
使用DFS深度遍历，值>或者<范围，都直接取小值方向

543. 二叉树的直径 Diameter of Binary Tree easy
法1. 时间复杂度O(n) 空间复杂度O(1)
最大值使用独立变量max保存，max=Math.max(max, l + r)，每次返回的值取Math.max(l, r) +1，

617. 合并两个二叉树 Merge Two Binary Trees easy
法1. 时间复杂度O(n) 空间复杂度O(n)
使用队列，BFS来处理，需要创建多出来的节点
法2. 时间复杂度O(n) 空间复杂度O(1)
todo

538. 把二叉查找树每个节点的值都加上比它大的节点的值 Convert BST to Greater Tree easy
法1. 时间复杂度O(n) 空间复杂度O(n)
由于二叉树是有序的，最右节点是最大的，使用DFS类似于逆向的中序遍历，从right->cur->left，使用一个sum累计之前节点的最值
法2. 时间复杂度O(n) 空间复杂度O(n)
使用Stack来实现DFS递归，核心的判断是while (!stack.isEmpty() || node != null)
法3. 时间复杂度O(n) 空间复杂度O(1)
morris方法 todo

530. Minimum Absolute Difference in BST easy
法1. 时间复杂度O(n) 空间复杂度O(1)
由于是BST，存在有序性，使用中序遍历，并用一个pre记忆前一个节点，使用min记忆绝对值最小值

235. 二叉查找树的最近公共祖先 Lowest Common Ancestor of a Binary Search Tree easy
法1. 时间复杂度O(n) 空间复杂度O(n)
由于是二叉查找树，因此树是有序的，因此只有值都大于或者小于目标值时，需要递归，剩余的都是公共祖先
法1. 时间复杂度O(n) 空间复杂度O(1)
使用非递归

701. 对二叉搜索树插入一个值，保持二叉搜索树规则 Insert into a Binary Search Tree
法1. 时间复杂度O(logn) 空间复杂度O(1)
使用折半查找
当node.val>val，说明值在node.left一边，这时候如果node.left==null直接加入节点，否则遍历node.left
否则说明值在node.right，这时候如果node.right==null直接加入节点，否则遍历node.right

2 无序二叉搜索树结点最小距离

783. 二叉搜索树结点最小距离 Minimum Distance Between BST Nodes easy
法1. 时间O(n), 空间O(1)，首先是无序二叉树的, 只要求2个节点（不是连线节点）的哪个是最小值即可，使用中序遍历，需要一个变量保存上一个节点的值，需要手写一次
法2. 时间O(2n)，空间O(n)，先按照中序遍历存储成列表，再计算两个值之间最小差值

4 无序二叉树最长同值路径（只能是一条路）

687. 最长同值路径 Longest Univalue Path medium
todo
一颗树，相同节点到节点（路过的节点也相同）最长路径
使用递归，O(n)，用全局变量保存最长路径值