- 知识点预习：
- 分治法： 先让左右子树去解决同样的问题， 然后得到结果之后， 再整合为整棵树的结果。
- 遍历法： 通过 前序/ 中序/ 后序 的某种遍历， 游走整棵树， 通过一个全局变量或者传递的参数来记录这个过程中所遇到的点 和 需要计算的结果。
- 两种方法的区别： 从实现分治法的角度递归函数， 通常有一个返回值， 遍历法通常没有。
- pre order
private void traversal( TreeNode root , List<Integer> result ) {
if( root == null) {
return ;
}
result.add( root.val);
traversal( root.left , result);
traversal( root.right , result);
}
- in order
private void traversal( TreeNode root , List<Integer> result ) {
if( root == null) {
return ;
}
traversal( root.left , result) ;
result.add(root.val);
traversal( root.right , result);
}
- post order
private void traversal( TreeNode root , List<Integer> result ) {
if( root == null) {
return ;
}
traversal( root.left);
traversal(root.right);
result.add(root.val);
}
- 二叉树上的分治法
- 二叉树最大深度
- 判断平衡二叉树
- 判断排序二叉树
- 用遍历法求 tree 的最大深度 : 遍历法 ; 通常没有 return value
int depth ;
public int maxDepth( TreeNode node) {
depth = 0;
travesal( root , 1);
return depth;
}
private void traversal( TreeNode node , int curDepth) {
if( node == null) {
return ;
}
depth = depth > curDepth ? depth : curDepth;
traversal( root.left , curDepth + 1);
traversal(root.right , curDepth + 1);
}
- 用 分治法 通常有 return value
- 这道题是 max depth 就是 左子树 和 右子树 中较大的depth + 1
public int maxDepth( TreeNode node) {
return helper( root);
}
private int helper(TreeNode root ) {
if(root == null) {
return 0;
}
int left = helper( root.left) + 1 ;
int right = helper(root.right )+ 1;
return Math.max(left , right);
}
- 判断平衡二叉树 : 分治法
- 平衡就 return 高度， 不平衡就return 不平衡
- 一边返回高度一边 判断是否是 平衡二叉树
private int NOT_BALANCED = -1;
public boolean isBalanced( TreeNode root) {
return maxDepth(root) != NOT_BALANCED;
}
private int maxDepth( TreeNode root ) {
if( root == null) {
return 0;
}
int left = maxDepth( root.left);
int right = maxDepth( root.right);
if( left == NOT_BALANCED || right == NOT_BALANCED) {
return NOT_BALANCED;
}
if( Math.abs( left - right) > 1) {
return NOT_BALANCED;
}
return Math.max( left , right) + 1;
}
- 判断二叉搜索树: 遍历法 vs 分治法
1 . 遍历法： 因为 BST 树的特性， inorder 的遍历法 就是一个 上升序列， 所以可以用 遍历法解决 。 遍历法 没有 return value， 但是有golbal 参数
private TreeNode lastNode;
private boolean isValid;
public boolean isValidBST( TreeNode root) {
isValid = true;
lasNode = null;
inorderTraverse(root);
return isValid;
}
private void inorderTraverse( TreeNode root) {
if( root == null ) {
return ;
}
inorderTraverse( root.left);
if( lastNode != null && lastNode.val >= root.val ) {
isValid = false;
return ;
}
lastNode = root;
inorderTraverse( root.right);
}
- 分治法 :
❌做法： 遍历到每个节点， 然后比较左右孩子
正确做法： current root 要比 左子树最大的值 ，还要大； 比右子树 的最小值还要小， 所以这道题 要return 2 个结果， min 和 max
class ResultType{
boolean isValid;
TreeNode minNode , maxNode;
public ResultType(boolean default) {
this.isValid = default;
this.minNode = null;
this.maxNode = null
}
}
public boolean isValid( TreeNode root) {
return divideConquer( root).isValid;
}
private ResultType divideConquer( TreeNode root ) {
if(root == null ) {
return new ResultType(true);
}
ResultType left = divideConquer( root.left);
ResultType right = divideConquer( root.right);
// 判断错误
if( ! left.isValid || !right.isValid) {
return new ResultType(false);
}
if( left.maxNode != null && root.val <= left.maxNode) {
return new ResultType(false);
}
if( right.minNode != null && root.val >=right.minNode ) {
return new ResultType(false);
}
// bst
ResultType res = new ResultType(true);
res.minNode = left.minNode == null ? root : left.minNode;
res.maxNode = right.maxNode == null ? root : right.maxNode;
return res;
}
知识点： 递归， 回溯 和 搜索
递归 ： 1 . 是一种由大化小， 由小化无的解决问题的算法。类似的算法还有动态规划。
2. 自己调用自己非递归：迭代法
-
- 什么是搜索（search）
- 搜索分为 深度优先搜索( DFS)和 宽度优先搜索（BFS）; 搜索通常是一种 类似于枚举的算法。
回溯法 就是 深度优先搜索。 回溯是 深度优先搜索过程中的一个步骤。
例如： 我们在进行全子集问题的搜索时 ，假如 当前的集合 是{1, 2} 代表我正在 寻找以{
1, 2} 开头的所有集合。 那么下一步 回去寻找 { 1, 2, 3} 开头的所有集合 ， 当然当我们找完所有以{1,2,3} 开头的集合时， 我们需要把3 从集合中 删除， 回到{1,2} . 然后 再把 4 放进去， 寻找以{1,2,4} 开头的集合。 这个把 3 删掉回到 {1, 2} 的过程， 就是回溯。bst定义： （BST）
- 若左子树 不为空， 则左子树上所有的节点值均小于 或等于它的根结点
- 若右子树不为空， 则右子树上所有的节点值均大于根节点值
- 左右子树也为二叉搜索树
平衡搜索树
- 空树可以是 balanced binary tree ； 2. 左右子树高度差不超过 <=1
特性 ：高度为 o（long n）
最大作用： 保证查找的最坏时间复杂度为 o(log n)
** 额外拓展：
- morris 算法实现 o(1) 额外空间对二叉树进行 先序遍历
- 用非递归（non-recusrion/ iteratioin）的方式实现二叉树的 前序遍历， 中序遍历 和 后序遍历
- BST 的增删改查
- 平衡排序二叉树（balanced binary search tree）以及 TreeSet / TreeMap 的使用
- 2 非递归的方式实现二叉树遍历
- 先序遍历 preorder
public List<Integer> preorderTraversal(TreeNode root) {
Stack<Integer> stack = new Stack<>();
List<Integer> result = new ArrayList<>();
TreeNode p = root;
stack.push( root);
while( !stack.empty() || p != null ) {
if( p != null ) {
stack.push( p);
result.add( p.val );
p = p.left;
} else {
TreeNode node = stack.pop();
p = p.right;
}
}
return result;
}
- 中序遍历
public List <Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> result = new ArrayList<>();
TreeNode p = root;
while( p != null || !stack.isEmpty() ) {
while( p != null) {
stack.push(p );
p = p.left;
}
TreeNode node = stack.pop();
result.add( node.val);
p = node.right
}
return result;
}
- 后序遍历
public List<Integer> postorderTraversal(TreeNode root) {
Stack< TreeNode> stack = new Stack<>();
List<Integer> result = new LinkedList<>();
TreeNode p = root ;
while( p != null || !stack.isEmpty() ) {
if( p != null) {
stack.add( p );
result.add( 0 , p);
p = p.left;
} else {
TreeNode node = stack.pop();
p = node.right;
}
}
return result;
}
- morris 算法实现 o(1) 额外空间对二叉树进行 先序遍历
preorder
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> nums = new ArrayList<>();
TreeNode cur = null;
while( root != null) {
if( root.left != null) {
cur = root.left;
}
while( cur.right != null && cur.right != root) {
cur = cur.right ;
}
if( cur.right == root) { // 撤销钩子
cur.right = null;
root = root.right;
} else { // cur.right == null
nums.add( root.val);
cur.right = root;
cur = root.left ;
}
} else {// root.left == null
nums.add(root.val);
root = root.right;
}
return nums;
}
- inorder
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> nums = new ArrayList<>();
TreeNode cur = null;
while( root != null) {
if( root.left != null ) {
cur = root.left ;
while( cur.right != null && cur.right != root) {
cur = cur.right ;
}
if( cur.right == root) {
nums.add(root);
root = root.right;
cur.right = null;
} else { // cur.right == null
cur.right = root;
root = root.left;
}
} else {
nums.add(root.val);
root = root.right;
}
}
}
- postorder
public List<Integer> inorderTraversal(TreeNode root) {
TreeNode cur = null;
List<Integer> nums = new ArrayList<>();
while( root != null) {
if（ root.right != null ） {
cur =root.right;
while( cur.left != null && cur.left != root) {
cur = cur.left;
}
if( cur.left == root) {
cur.left = null;
root = root.left;
} esle {
cur.left = root;
nums.add(root.val);
root = root.right;
}
} else {
nums.add(root.val);
root = root.left;
}
}
Collections.reverse( nums);
return nums;
}
BST 的增删改查
- 在求 BST 的 时间复杂度追求 ： O（log N）
closestValue ： 找到 pre ， suc 然后比较
two sum: 用 pre ， suc + 双指针
BST 里面要知道如何求 predecessor 和 successor
predecessor：
private TreeNode inorderPredecesor (TreeNode root , TreeNode node ) {
TreeNode res = null;
while( root != null) {
if( root.val > node.val) {
root = root.left;
} else { // root.val <= node.val
res = root;
root = root.right；
}
}
return res;
}
successor
private TreeNode inorderSuccessor ( TreeNode root , TreeNode node ) {
TreeNode res = null；
while( root != null) {
if( root.val < node.val ) {
root = root.right ;
} else { // root.val >= node.val
res = root;
root = root.left ;
}
}
return res;
}
BST 删除
BST 插入
BST 修改
BST 查找
- http://www.lintcode.com/en/problem/search-range-in-binary-search-tree/
- http://www.lintcode.com/en/problem/two-sum-bst-edtion/
- http://www.lintcode.com/en/problem/closest-binary-search-tree-value/
- http://www.lintcode.com/en/problem/closest-binary-search-tree-value-ii/
- http://www.lintcode.com/en/problem/trim-binary-search-tree/
- http://www.lintcode.com/en/problem/bst-swapped-nodes/
======================================================================
1.Kth Largest Element in an Array（215. leetcode）
public int findKthLargest( int [] nums, int k){
if( nums == null || nums.length == 0)
return -1;
return quickSelect( nums, 0, nums.length - 1, nums.length - k + 1);
}
private int quickSelect(int [] nums , int start , int end , int k ) {
if(start == end) return nums[ start];
int mid = start + (end - start )/2 ;
int pivot = nums[ mid];
int i =start , j = end;
while( i <= j ){
while( i <= j && nums[ i ] < pivot) i ++;
while( i <= j && nums[ j] < pivot ) j -- ;
if( i <= j) {
int tmp = nums[i];
nums[ i] = nums[ j];
nums[ j ] = tmp;
i ++;
j -- ;
} / * if */
} / * while */
if ( start + k - 1 <= j ){
return quickSelect( nums, start, j , k );
} else if ( start + k - >=i ) {
return quickSelect( nums, i , end , k - i + start);
}
return nums[ j + 1];
}
2. Closest Binary Search Tree Value II (google )
- getStack() : 到达离 target 最近的 node 时， 所经过的点
- moveUpper( stack) : 根据 stack ， 挪动到 next node
- moveLower( stack) : 根据 stack ， 挪动到 prev node
有了这些函数之后， 就可以把整棵树当做一个数组一样来处理， 只不过每次 i++ 的时候要用
moveUpper , i -- 的时候要用 moveLower
public List<Integer> closestKValues(TreeNode root, double target, int k) {
List< Integer> values = new ArrayList<>();
if( k == 0 || root == null) {
return values;
}
Stack<TreeNode> lowerStack = getStack();
Stack<TreeNode> upperStack = new Stack<>();
upperStack.addAll( lowerStack) ;
if( target < lowerStack.peek().val ) {
moveLower( lowerStack);
} else {
moveUpper( upperStack);
}
for( int i =0 ; i < k ; i++) {
if( lowerStack.isEmpty() || target - lowerStack.peek().val > upperStack().peek().val - target) { values.add(upperStack.peek().val )
moveUpper( upperStack);
} else {
values.add( lowerStack.peek().val );
moveLower( lowerStack);
}
}
return values;
}
private Stack<TreeNode > getStack( TreeNode root , double target ) {
Stack<TreeNode > res = new Stack <>();
while( root != null) {
res.push( root );
if( root.val > target) {
root = root.left ;
} else { // root.val <= target
root = root.right;
}
}
return res;
}
private void moveUpper( Stack<TreeNode> stack) {
TreeNode node = stack.peek();
if( node.right == null) {
node = stack.pop();
while( !stack.isEmpty() || stack.peek().right == node ) {
node = stack.pop();
}
return ;
}
node = node.right;
while( node != null) {
stack.add(node);
node = node.left;
}
}
private void moveLower( Stack<TreeNode > stack ) {
TreeNode node = stack.peek();
if( node.left == null ) {
node = stack.pop();
while( stack.isEmpty() || stack.peek().left != node ) {
node = stack.pop() ;
}
return;
}
// node.left != null 说明有prev node
node = node.left;
while( node != null) {
stack.push( node);
node = node.right;
}
}
