目录
- Convert/Create
- 99 Recover Binary Search Tree
- 108 Convert Sorted Array to Binary Search Tree
- 109 Convert Sorted List to Binary Search Tree
- 538 Convert BST to Greater Tree
- 1038 Binary Search Tree to Greater Sum Tree
- 173 Binary Search Tree Iterator
- 449 Serialize and Deserialize BST
- 1008 Construct Binary Search Tree from Preorder Traversal
- Valid/Unique
- Delete/Insert/Count
- Search
- Find
- Other
A BST Definition
public class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){val = x;}
}
[Convert/Create to BST]
#99 Recover Binary Search Tree
BST中有两个node出现错误，需要在不改变结构的情况下交换节点
-
Sol: In-order, Recursion
中序遍历的特性, 标记乱序点，第一个乱取点取最大值，第二个乱取点取最小的乱序点。交换
TreeNode pre = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
TreeNode[] swap = new TreeNode[2];
help(root, swap);
if(swap[0] != null && swap[1] != null){
int tmp = swap[0].val;
swap[0].val = swap[1].val;
swap[1].val = tmp;
}
}
public void help(TreeNode cur, TreeNode[] swap){
if(cur == null){return;}
help(cur.left, swap);
if(pre.val >= cur.val){
if(swap[0] == null){
swap[0] = pre;
}
if(swap[0] != null){
swap[1] = cur;
}
}
pre = cur;
help(cur.right, swap);
}
- Sol: In-order, Iteration
public void recoverTree(TreeNode root) {
TreeNode pre = new TreeNode(Integer.MIN_VALUE);
TreeNode first = null, second = null;
Stack<TreeNode> s = new Stack<>();
while(root!=null || !s.isEmpty()){
while(root != null){
s.push(root);
root = root.left;
}
root = s.pop();
if(pre.val > root.val){
if(first == null){
first = pre;
}
if(first != null){
second = root;
}
}
pre = root;
root = root.right;
}
Swap(first, second);
}
public void Swap(TreeNode first, TreeNode second){
if(first != null && second != null){
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
}
#108 Convert Sorted Array to Binary Search Tree
- Sol: 递归构建
- 先得到数组元素的中间元素，将它的值作为根节点
- 并且以它为中间中介，将数组划分为左右区间。根节点的左子树指向左区间，右节点指向右区间。
- 再针对左右区间进行同样的操作。直到左指针和右指针重合。
public TreeNode sortedArrayToBST(int[] nums) {
return dfs(nums, 0, nums.length-1);
}
public TreeNode dfs(int[] nums, int start, int end) {
if(end < start){return null;}
int mid = start + (end - start) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = sortedArrayToBST(nums, start, mid-1);
root.right = sortedArrayToBST(nums, mid+1, end);
return root;
}
知识点--二分搜索算法（binary search）
二分搜索只对有序数组有效。
public static int binarySearch(int[] arr, int start, int end, int hkey){
if (start > end)
return -1;
int mid = start + (end - start)/2; //防止溢位
if (arr[mid] > hkey)
return binarySearch(arr, start, mid - 1, hkey);
if (arr[mid] < hkey)
return binarySearch(arr, mid + 1, end, hkey);
return mid;
}
#109 Convert Sorted List to Binary Search Tree
-
Sol1: 将单链表中的值存入一个数组中
通过数组来构建二叉树，算法时间复杂度是：O(n)，空间复杂度是：O(n) -
Sol2: 二分归并|递归实现|快慢指针
A LinkedList Definition
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public TreeNode sortedListToBST(ListNode head) {
return rec(head, null);
}
private TreeNode rec(ListNode start, ListNode end) {
if(end == start){return null;}
ListNode p = start, q = start;
while(q.next != end && q.next.next != end){
p = p.next;
q = q.next.next;
}
TreeNode root = new TreeNode(p.val);
root.left = rec(start, p);
root.right = res(p.next, end);
return root;
}
#538 Convert BST to Greater Tree
- Sol 中序遍历-先右支
private int sum = 0;
public TreeNode convertBST(TreeNode root) {
if(root == null){return null;}
convertBST(root.right);
root.val += sum;
sum = root.val;
convertBST(root.left);
return root;
}
#1038 Binary Search Tree to Greater Sum Tree
- Sol 中序遍历
int sum = 0;
public TreeNode bstToGst(TreeNode root) {
if(root == null){return root;}
bstToGst(root.right);
sum += root.val;
root.val = sum;
bstToGst(root.left);
return root;
}
#173 Binary Search Tree Iterator
- Sol 中序遍历+栈
Stack<TreeNode> s;
public BSTIterator(TreeNode root) {
s = new Stack<>();
help(root);
}
public void help(TreeNode root){
if(root == null){return;}
help(root.right);
s.add(root);
help(root.left);
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !s.isEmpty();
}
/** @return the next smallest number */
public int next() {
return s.pop().val;
}
#449 Serialize and Deserialize BST
ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.
- **Sol pre order traversal **
recursively convert with the lower and upper boundary check
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder res = new StringBuilder();
helpSer(root, res);
return new String(res);
}
public void helpSer(TreeNode root, StringBuilder s){
if(root == null) return;
s.append((char)root.val);
helpSer(root.left, s);
helpSer(root.right, s);
}
// Decodes your encoded data to tree.
int index = 0;
public TreeNode deserialize(String data) {
char[] input = data.toCharArray();
return helpDes(input , Integer.MIN_VALUE , Integer.MAX_VALUE);
}
public TreeNode helpDes(char[] data, int min, int max){
if(index >= data.length || Integer.valueOf(data[index]) >= max || Integer.valueOf(data[index]) <= min){return null;}
TreeNode root = new TreeNode(Integer.valueOf(data[index++]));
root.left = helpDes(data, min, Integer.valueOf(root.val));
root.right = helpDes(data, Integer.valueOf(root.val), max);
return root;
}
#1008 Construct Binary Search Tree from Preorder Traversal
- Sol
int index = 0;
public TreeNode bstFromPreorder(int[] preorder) {
if(preorder.length == 0){return null;}
return help(preorder, 0, preorder.length-1);
}
public TreeNode help(int[] list, int start, int end){
if(start > end || index == list.length) return null;
TreeNode root = new TreeNode(list[index++]);
if(start == end){return root;}
int i = 0;
for(i = start; i <= end; i++){
if(list[i] > root.val) break;
}
root.left = help(list, index, i-1);
root.right = help(list, i, end);
return root;
}
[Valid/Unique]
#98 Validate Binary Search Tree
BST特性：
root.Left中所有节点的最大值小于root.Val
root.Right中所有节点的最小值大于root.Val
-
sol1 Recursion
考虑root为Integer.MIN_VALUE的情况
//Recursion
public boolean isValidBST(TreeNode root) {
return help(root, null, null);
}
public boolean help(TreeNode root, Integer min, Integer max) {
if(root == null) return true;
int val = root.val;
if((min!=null && val <= min) ||(max != null && val >= max)) return false;
return help(root.left, min, val) && help(root.right, val, max);
}
Time complexity : O(N) since we visit each node exactly once.
Space complexity : O(N) since we keep up to the entire tree.
-
sol2 Iteration
利用Stack改写递归过程
//Iteration
class Solution {
public boolean isValidBST(TreeNode root) {
LinkedList<TreeNode> s = new LinkedList<>();
LinkedList<Integer> left = new LinkedList<>();
LinkedList<Integer> right = new LinkedList<>();
s.add(root);
left.add(null);
right.add(null);
Integer l = null;
Integer r = null;
while(!s.isEmpty()){
root = s.poll();
l = left.poll();
r = right.poll();
if(root == null)continue;
if(l!=null && l >= root.val) return false;
if(r!=null && r <= root.val) return false;
s.add(root.left);
left.add(l);
right.add(root.val);
s.add(root.right);
left.add(root.val);
right.add(r);
}
return true;
}
}
Time complexity : O(N) since we visit each node exactly once.
Space complexity : O(N) since we keep up to the entire tree.
-
sol3 Inorder traversal
中序遍历
special test case: [-2147483648]
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> s = new Stack<>();
Integer tmp = null;
while(root!=null || !s.isEmpty()){
while(root != null){
s.add(root);
root = root.left;
}
root = s.pop();
if(tmp != null && root.val <= tmp) return false;
tmp = root.val;
root = root.right;
}
return true;
}
Time complexity : O(N) in the worst case when the tree is BST or the "bad" element is a rightmost leaf.
Space complexity : O(N) to keep stack.
#96 Unique Binary Search Trees
输入n，输出由1...n组成不同的BST的个数
-
Sol 一维动态规划
dp[i]为[1, i]产生的Unique BST个数, i为跟节点，左子树个数为[1, i-1]右子树个数为[i+1, n]；
dp[0] = 1
dp[1] = 1
dp[2] = dp[1] * dp[0] + dp[0] * dp[1]
dp[3] = dp[0] * dp[2] + dp[2] * dp[0] + dp[1] * dp[1]
递推公式可得dp[i]=dp[0]dp[i-1]+...+dp[k-1]dp[i-k]+...+dp[i-1]*dp[0]
public int numTrees(int n) {
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i < n+1; i++){
for(int j = 0; j < i; j++){
dp[i] += dp[j] * dp[i-1-j];
}
}
return dp[n];
}
#95 Unique Binary Search Trees II
输出用1–n这几个数字能组成的所有BST
-
Sol 动态规划
选出根结点后应该先分别求解该根的左右子树集合,然后将左右子树相互配对,把根结点放入链表中.
public List<TreeNode> generateTrees(int n) {
if(n < 1){return new ArrayList<TreeNode>();}
return help(1, n);
}
public List<TreeNode> help(int start, int end){
List<TreeNode> res = new ArrayList<>();
if(start > end){
res.add(null);
return res;
}
for(int i = start; i <= end; i++){
List<TreeNode> left = help(start, i-1);
List<TreeNode> right = help(i+1, end);
for(TreeNode l : left){
for(TreeNode r : right){
TreeNode root = new TreeNode(i);
root.left = l;
root.right = r;
res.add(root);
}
}
}
return res;
}
[Delete/Insert/Count]
#701 Insert into a Binary Search Tree*
不需要平衡，只需要插入
-
Sol BST的特性+递归
遇到空就直接插入就好了
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null){return new TreeNode(val);}
if(root.val < val){
root.right = insertIntoBST(root.right, val);
}else{
root.left = insertIntoBST(root.left, val);
}
return root;
}
#222 Count Complete Tree Nodes
完全二叉树节点数统计
-
Sol1 对二叉树进行遍历
最直接的方法是对二叉树进行遍历，然后逐个节点进行统计，时间复杂度是O(n)，n为节点数量。
==>Time Limited Exceeded -
Sol2 BST特性
如果右子树的高度等于整棵二叉树的高度-1的话，那么左子树一定是一棵满二叉树，这个时候我们就很容易的计算出总结点数nodes=2(h)-1 + 1 +右子树节点数（这里的+1表示root节点）。如果右子树的高度不等于整棵二叉树的高度-1的话，那么左子树不一定是一棵满二叉树，但是有一点可以确定，右子树一定是一棵满二叉树，这个时候我们就很容易的计算出总结点数nodes=2(h-1)-1 + 1 +左子树节点数（这里的+1表示root节点）。
public int countNodes(TreeNode root) {
if(root == null){return 0;}
int right_height = height(root.right);
int root_height = height(root);
if(right_height == root_height - 1){
return 1 +(int)Math.pow(2, root_height-1) - 1 + countNodes(root.right);
}else{
return 1 + (int)Math.pow(2, right_height) - 1 + countNodes(root.left);
}
}
public int height(TreeNode r){
int height = 0;
while(r != null){
r = r.left;
height++;
}
return height;
}
#450 Delete Node in a BST
删除BST中节点
Time complexity should be O(height of tree)
- Sol 二分搜索寻找key + 递归处理key节点 + 递归处理旁枝
- 原函数递归, 如果root.Val大于key，那就让左边处理root.Left = deleteNode(root.Left, key)，否则让有右边处理，最后返回root
如果root.Val等于key，那我们规定把左边的点递上来: - -- 如果root没有左叶子，那么直接返回root的右叶子，因为root需要被删除
-- 如果root的左叶子存在：- 如果root的右叶子不存在，那么直接返回root的左叶子
- 存储root.Left.Right到tmp, 然后让root.Left.Right = root.Right，最后在root.Right 中插入 tmp，由BST特性可知，tmp中所有数肯定小于root.Right，递归找到root.Right的最左侧，插入即可。
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null){return root;}
if(root.val == key){
return help(root);
}
if(root.val < key){
root.right = deleteNode(root.right, key);
}else{
root.left = deleteNode(root.left, key);
}
return root;
}
public TreeNode help(TreeNode root){
if(root.left == null){
return root.right;
}
if(root.right == null){
return root.left;
}
TreeNode tmp = root.left.right;
root.left.right = root.right;
TreeNode end = root.right;
while(end.left != null){
end = end.left;
}
end.left = tmp;
return root.left;
}
#669 Trim a Binary Search Tree
- Sol Recursion
public TreeNode trimBST(TreeNode root, int L, int R) {
if(root == null){return null;}
if(root.val < L){
return trimBST(root.right, L, R);
}
if(root.val > R){
return trimBST(root.left, L, R);
}
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
return root;
}
Time Complexity:O(N) We visit each node at most once.
Space Complexity: O(N). Even though we don't explicitly use any additional memory, the call stack of our recursion could be as large as the number of nodes in the worst case.
#563 Binary Tree Tilt
- Sol
int sum = 0;
public int findTilt(TreeNode root) {
help(root);
return sum;
}
public int help(TreeNode root){
if(root == null){return 0;}
int left = help(root.left);
int right = help(root.right);
sum += Math.abs(left - right);
return left + right + root.val;
}
[Search]
#700 Search in a Binary Search Tree
根据BST特性, 有二分搜索的效果
因为比root小的元素全部在root.Left，比root大的元素全部在root.Right
- Sol
public TreeNode searchBST(TreeNode root, int val) {
if(root == null){return null;}
if(root.val == val){return root;}
if(root.val < val){return searchBST(root.right, val);}
else{return searchBST(root.left, val);}
}
#653 Two Sum IV - Input is a BST
- Sol inorder
List<Integer> l = new ArrayList<>();
public boolean findTarget(TreeNode root, int k) {
inorder(root);
for(int i = 0, j = l.size()-1; i < j;){
int sum = l.get(i) + l.get(j);
if(sum == k) return true;
if(sum < k)i++;
else j--;
}
return false;
}
public void inorder(TreeNode root){
if(root == null){return;}
inorder(root.left);
l.add(root.val);
inorder(root.right);
}
#662 Maximum Width of Binary Tree
** Sol1 BFS**
public int widthOfBinaryTree(TreeNode root) {
if(root == null){return 0;}
int res = 1;
Deque<TreeNode> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
while(!q.isEmpty() && q.peek()==null){
q.poll();
}
while(!q.isEmpty() && q.peekLast()==null){
q.pollLast();
}
// System.out.println(q.size());
res = Math.max(res, q.size());
int size = q.size();;
for(int i = 0; i < size; i++){
TreeNode cur = q.poll();
if(cur == null){
q.add(null);
q.add(null);
}else{
if(cur.left != null) q.add(cur.left);
else{q.add(null);}
if(cur.right != null) q.add(cur.right);
else{q.add(null);}
}
}
}
return res;
}
- Sol2 DFS + HashMap
int res;
Map<Integer, Integer> map;
public int widthOfBinaryTree(TreeNode root) {
res = 0;
map = new HashMap<>();
help(root, 0, 0);
return res;
}
public void help(TreeNode root, int level, int pos){
if(root == null) return;
map.computeIfAbsent(level, x->pos);
res = Math.max(res, pos - map.get(level) + 1);
help(root.left, level+1, pos * 2);
help(root.right, level+1, pos*2+1);
}
Time O(n)
Space O(n)
[Find]
#530 Minimum Absolute Difference in BST
BST最小绝对值差
- Sol1 中序遍历--迭代
public int getMinimumDifference(TreeNode root) {
int res = Integer.MAX_VALUE;
Stack<TreeNode> s = new Stack<>();
TreeNode tmp_root = null;
while(!s.isEmpty() || root != null){
while(root!=null){
s.push(root);
root = root.left;
}
root = s.pop();
if(tmp_root!=null){
int tmp = Math.abs(root.val - tmp_root.val);
if(tmp < res){
res = tmp;
}
}
tmp_root = root;
root = root.right;
}
return res；
}
- Sol2 中序遍历--递归
int res = Integer.MAX_VALUE;
TreeNode last = null;
public int getMinimumDifference(TreeNode root) {
if(root == null){return res;}
res = getMinimumDifference(root.left);
if(last!=null){
res = Math.min(res, Math.abs(root.val - last.val));
}
last = root;
return getMinimumDifference(root.right);
}
#230 Kth Smallest Element in a BST
使用BST的中序遍历特性
-
Sol1: 中序遍历, 递归实现
BST的中序遍历必定是严格递增的。
public int count, res;
public int kthSmallest(TreeNode root, int k){
if(root.left!=null){kthSmallest(root.left, k);}
if(++count == k){res = root.val;}
if(root.right!=null){kthSmallest(root.right, k);}
return res;
}
- Sol2: 非递归实现，栈
int res = 0;
Stack<TreeNode> s = new Stack<>();
while(true){
while(root != null){
s.push(root);
root = root.left;
}
if(!s.isEmpty()){
root = s.pop();
if(--k == 0){return root.val;}
root = root.right;
}else{break;}
}
return 0;
#501 Find Mode in Binary Search Tree
找众数
-
Sol1 HashMap
构造一个哈希表，记录数字和其出现次数之前的映射，同时变量mx记录当前最多的次数值。
遍历完树之后，根据mx值就能把对应的元素找出来。用随意一种遍历方式都可以。 - Sol2 中序遍历
List<Integer> res = new ArrayList<>();
int count = 1;
Integer pre = null;
int max = 0;
public int[] findMode(TreeNode root) {
help(root);
int[] result = new int[res.size()];
for (int i = 0; i < res.size(); ++i) result[i] = res.get(i);
return result;
}
public void help(TreeNode root){
if(root == null){return;}
help(root.left);
if(pre != null){
if(root.val == pre){
count++;
}else{
count = 1;
}
}
if(count > max){
max = count;
res.clear();
res.add(root.val);
}else if( count == max){
res.add(root.val);
}
pre = root.val;
help(root.right);
}
#235 Lowest Common Ancestor of a Binary Search Tree
BST最近公共祖先
- Sol Recursive
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(p.val > root.val && q.val > root.val){
return lowestCommonAncestor(root.right, p, q);
}else if(q.val < root.val && p.val < root.val){
return lowestCommonAncestor(root.left, p, q);
}else{
return root;
}
}
#783 Minimum Distance Between BST Nodes
- Sol Recursive, in-order
int res = Integer.MAX_VALUE;
Integer pre = null;
public int minDiffInBST(TreeNode root) {
if(root == null){return res;}
minDiffInBST(root.left);
if(pre != null){
res = Math.min(res, root.val - pre);
}
pre = root.val;
minDiffInBST(root.right);
return res;
}
[Other]
**#968## Binary Tree Cameras
给定一棵二叉树，要求在上面一些结点上放照相机（照相机可以覆盖结点自己、它的父结点和子结点），使得所有的结点都被覆盖，且被放照相机的结点总数最少。
-
Sol1 动态规划DP
节点（cur_node）的状态：
状态0: 两个子节点均被覆盖，当前节点不被覆盖。
状态1: 当前节点与两个子节被覆盖，但是当前节点没有放置相机
状态3: 当前节点放置了相机
状态转移条件：
令solve（node）函数为求解函数（递归函数）：
- 为了满足状态0，则cur_node的两个子节点都必须处于状态1。当node为状态0时，返回覆盖其子树所有节点所需的最小相机数(dp[0])
- 为了满足状态1，则cur_node的两个子节点中至少有一个子节点处于状态2，另一个子节点处于状态1或状态2。当node为状态1时，返回覆盖其子树所有节点所需的最小相机数(dp[1])
- 对于状态2，由于cur_node放置相机，两个子节点可以处于任何状态。当node为状态2时，返回覆盖其子树所有节点所需的最小相机数(dp[2])
由于状态0没有覆盖到当前节点，因此要求解覆盖包含当前节点的最优解时，其解为min(dp[1], dp[2])。
递归出口：
当当前节点为NULL时，跳出递归
public int minCameraCover(TreeNode root) {
int[] res = slove(root);
return Math.min(res[1], res[2]);
}
public int[] slove(TreeNode root){
if(root == null){
return new int[]{0, 0, 99999};
}
int[] L = slove(root.left);
int[] R = slove(root.right);
int minL = Math.min(L[1], L[2]);
int minR = Math.min(R[1], R[2]);
int d0 = L[1] + R[1];
int d1 = Math.min(L[2] + minR, R[2] + minL);
int d2 = 1 + Math.min(L[0], minL) + Math.min(R[0], minR);
return new int[]{d0, d1, d2};
}
Time Complexity: O(N), where NN is the number of nodes in the given tree.
Space Complexity:O(H), where HH is the height of the given tree.
知识点--树的遍历
- 深度优先遍历
- 前序遍历 Pre-Order Traversal
指先访问根，然后访问子树的遍历方式
- 前序遍历 Pre-Order Traversal
// Do Something with root
if (root->lchild != NULL)
pre_order_traversal(root->lchild);
if (root->rchild != NULL)
pre_order_traversal(root->rchild);
- 中序遍历 In-Order Traversal
先访问左（右）子树，然后访问根，最后访问右（左）子树的遍历方式
if (root->lchild != NULL)
in_order_traversal(root->lchild);
// Do Something with root
if (root->rchild != NULL)
in_order_traversal(root->rchild);
- 后序遍历 Post-Order Traversal
先访问子树，然后访问根的遍历方式
if (root->lchild != NULL)
post_order_traversal(root->lchild);
if (root->rchild != NULL)
post_order_traversal(root->rchild);
// Do Something with root
- 广度优先遍历
又称按层次遍历, 算法借助队列实现。
