538. Convert BST to Greater Tree
Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.
Example:
Input: The root of a Binary Search Tree like this:
5
/
2 13
Output: The root of a Greater Tree like this:
18
/
20 13
题意就是每个节点的值是本身加上所有比它大的节点的值，所有最右边是所有节点的和20。BST一定要想到inorder遍历。这道题反过来in order遍历。
class Solution {
int sum = 0;
public TreeNode convertBST(TreeNode root) {
// inverse inorder traversal
// right root left
if (root == null) {
return null;
}
convertBST(root.right);
root.val = root.val + sum;
sum = root.val;
convertBST(root.left);
return root;
}
}
315. Count of Smaller Numbers After Self
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example:
Given nums = [5, 2, 6, 1]
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Return the array [2, 1, 1, 0].
有两个点。一是找5以后比5小的数，要想到可以从后往前找。二是想到构建一个二叉树来解题，node里再存一个count记录左子树的个数。有几个细节没想清楚，一是如果出现相等的数字怎么办。二是把结果的list当参数传进去。最后学习如何手写一个BST。
class Solution {
/**
1. add into tree reversely
2. how to handle equally
*/
public List<Integer> countSmaller(int[] nums) {
List<Integer> res = new ArrayList<>();
// construct a binary search tree
BST bst = new BST();
// add from right to left
for (int i = nums.length - 1; i >= 0; i--) {
bst.insert(nums[i], res);
}
Collections.reverse(res);
return res;
}
class TreeNode {
TreeNode left, right;
int count; // number of nodes in the left substree
int val; // root's value
public TreeNode(int val) {
this.count = 0;
this.left = this.right = null;
this.val = val;
}
}
class BST {
TreeNode root;
public BST () {
root = null;
}
public void insert (int num, List<Integer> res) {
root = insert(root, num, 0, res);
}
private TreeNode insert(TreeNode node, int val, int sum, List<Integer> res) {
if (node == null) {
node = new TreeNode(val);
res.add(sum);
return node;
}
if (node.val > val) {
node.count++;
node.left = insert(node.left, val, sum, res);
} else {
node.right = insert(node.right, val, sum + node.count + (node.val == val ? 0 : 1), res);
}
return node;
}
}
}
199. Binary Tree Right Side View
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,
1 <---
/
2 3 <---
\
5 4 <---
You should return [1, 3, 4].
用level order做。需要注意的是一开始没有考虑到这种情况。
1
/
2 3
\
5
655. Print Binary Tree
Input:
1
/
2 3
4
Output:
[["", "", "", "1", "", "", ""],
["", "2", "", "", "", "3", ""],
["", "", "4", "", "", "", ""]]
数组的长度是树的宽度，个数是树的高度，用分治做，递归函数有哪些参数需要注意。剩下就是细节，Math函数返回double，list如何在指定位置插入。最好把结果的二维list初始化好 这样更方便。
class Solution {
public List<List<String>> printTree(TreeNode root) {
// get the height and width of the given tree
int height = getHeight(root);
int width = (int) Math.pow(2, height) - 1; // pow return double
List<List<String>> res = new ArrayList<>();
for (int i = 0; i < height; i++) {
List<String> list = new ArrayList<>();
for (int j = 0; j < width; j++) {
list.add("");
}
res.add(list);
}
// fill the list of each level
helper(root, res, 0, 0, width - 1);
return res;
}
// helper function, fill list
public void helper(TreeNode root, List<List<String>> res, int level, int left, int right) {
if (root == null) {
return;
}
int mid = (left + right) / 2;
res.get(level).set(mid, String.valueOf(root.val));
helper(root.left, res, level + 1, left, mid - 1);
helper(root.right, res, level + 1, mid + 1, right);
}
public int getHeight(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}
}
遍历
- 前序
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> preorder = new ArrayList<Integer>();
if (root == null) {
return preorder;
}
stack.push(root);
while (!stack.empty()) {
TreeNode node = stack.pop();
preorder.add(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return preorder;
}
- Level Order
- In Order
543. Diameter of Binary Tree
Given a binary tree
1
/
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
用MaxDepth做
173. Binary Search Tree Iterator
Implement an iterator of a BST, next() and hasNext()
BST的inorder traversal是有序的，关键是弹出leftmost之后如何能找到父亲节点，想到用stack
关键是知道BST的inorder和使用stack保存父亲节点
98. Validate Binary Search Tree
如题
一种是分治，分到左右子树。把当前value传到左子树做最大值，传到右子树做最小值，如果当前值小于最大值，大于最小值，而且左右子树都true，那么返回true。感觉跟正常的分治有点区别。
BST要想到inorder遍历，用stack记录每个左节点，到了leftmost之后开始pop，存在右节点就处理右节点，没有就再pop获取其父亲。然后pop出来，再处理右节点
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.empty()){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
list.add(root.val);
root = root.right;
}
return list;
}
314. Binary Tree Vertical Order Traversal
- 观察得知用level order遍历
- 每个node还需要有一个offset信息 （root是0，左孩子是-1，右孩子是1）想到用另一个queue和level order的queue同步更新
- Keep track of leftmost and rightmost，最后从hashmap拿数据时候用
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
// column - points
Map<Integer, List<Integer>> map = new HashMap<>();
// traverse the tree
Queue<TreeNode> q = new LinkedList<>();
Queue<Integer> c = new LinkedList<>();
q.offer(root);
c.offer(0);
// keep track of leftmost and rightmost
int left = 0, right = 0;
while(!q.isEmpty()) {
int column = c.poll();
TreeNode cur = q.poll();
if (map.containsKey(column)) {
map.get(column).add(cur.val);
} else {
List<Integer> list = new ArrayList<>();
list.add(cur.val);
map.put(column, list);
}
if (cur.left != null) {
q.offer(cur.left);
c.offer(column - 1);
left = Math.min(left, column - 1);
}
if (cur.right != null) {
q.offer(cur.right);
c.offer(column + 1);
right = Math.max(right, column + 1);
}
}
for (int i = left; i <= right; i++) {
res.add(map.get(i));
}
return res;
}
652. Find Duplicate Subtrees
Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.
Two trees are duplicate if they have the same structure with same node values.
递归的序列化每个子树
class Solution {
// serialize the tree
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
Map<String, Integer> map = new HashMap<>(); // store every serialized subtree, if duplicate store it into res
List<TreeNode> list = new ArrayList<>();
serialize(root, map, list);
return list;
}
public String serialize(TreeNode node, Map<String, Integer> map, List<TreeNode> list) {
if (node == null) {
return "#";
}
String key = node.val + "," + serialize(node.left, map, list) + "," + serialize(node.right, map, list);
map.put(key, map.getOrDefault(key, 0) + 1);
if (map.get(key) == 2) {
list.add(node);
}
return key;
}
}
