-
Binary Tree Con.
(6) Structure of Tree- 100 Same Tree
- 101 Symmetric Tree
- 965 Univalued Binary Tree
- 958 Check Completeness of a Binary Tree
- 951 Flip Equivalent Binary Trees
(7) SubTree/Leaves
(8) Other BT
-
BST(补充)
-
Other Tree
[Binary Tree Con.][Structure of Tree]
#100 Same Tree
Easy
- Sol1 Recursive
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) return true;
if(p == null || q == null) return false;
if(p.val == q.val) return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
return false;
}
Time complexity : O(N), where N is a number of nodes in the tree, since one visits each node exactly once.
Space complexity : O(log(N)) in the best case of completely balanced tree and O(N) in the worst case of completely unbalanced tree, to keep a recursion stack.
- Iterative
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) return true;
if(!check(p, q)) return false;
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();
s1.add(p);
s2.add(q);
while(!s1.isEmpty()){
TreeNode n1 = s1.pop();
TreeNode n2 = s2.pop();
if(!check(n1,n2))
return false;
if(n1 != null) {
s1.push(n1.left);
s2.push(n2.left);
s1.push(n1.right);
s2.push(n2.right);
}
}
return true;
}
public boolean check(TreeNode p, TreeNode q){
if(p == null && q == null) return true;
if(p == null || q == null) return false;
if(p.val != q.val) return false;
return true;
}
Time complexity : O(N), where N is a number of nodes in the tree, since one visits each node exactly once.
Space complexity : O(log(N)) in the best case of completely balanced tree and O(N) in the worst case of completely unbalanced tree, to keep a recursion stack.
#101 Symmetric Tree
- Sol1 Recursive
public boolean isSymmetric(TreeNode root) {
return help(root, root);
}
public boolean help(TreeNode t1, TreeNode t2){
if(t1 == null && t2 == null) return true;
if(t1 == null || t2 == null) return false;
if(t1.val == t2.val) return help(t1.left, t2.right) && help(t1.right, t2.left);
return false;
}
Time O(n)
Space O(n)
- Sol2 Iterative
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
q.add(root);
while(!q.isEmpty()){
TreeNode t1 = q.poll();
TreeNode t2 = q.poll();
if(t1 == null && t2 == null) continue;
if(t1 == null || t2 == null) return false;
if(t1.val != t2.val) return false;
q.add(t1.left);
q.add(t2.right);
q.add(t1.right);
q.add(t2.left);
}
return true;
}
Time O(n)
Space O(n)
#965 Univalued Binary Tree
- Sol1 Recursive
public boolean isUnivalTree(TreeNode root) {
if(root == null) return true;
if(root.left != null || root.right != null){
if(root.left == null) return root.val == root.right.val && isUnivalTree(root.right);
if(root.right == null) return root.val == root.left.val &&isUnivalTree(root.left);
return root.val == root.right.val && root.val == root.left.val && isUnivalTree(root.left) && isUnivalTree(root.right);
}
return true;
}
Time: O(n)
Space: O(H) height
#958 Check Completeness of a Binary Tree
- Sol BFS
public boolean isCompleteTree(TreeNode root) {
if(root == null) return true;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
int level = 0;
while(!q.isEmpty()){
int size = q.size();
boolean check = true;
for(int i = 0; i < size; i++){
TreeNode cur = q.poll();
if(cur.left != null && size != 1 << level) return false;
if(cur.left != null) {
if(!check) return false;
q.add(cur.left);
}else check = false;
if(cur.right != null) {
if(!check) return false;
q.add(cur.right);
}else check = false;
}
level++;
}
return true;
}
Time O(N)
Space O(N)
#951 Flip Equivalent Binary Trees
- Sol Recursive
public boolean flipEquiv(TreeNode root1, TreeNode root2) {
if(root1 == null && root2 == null) return true;
if(root1 == null || root2 == null) return false;
if(root1.val == root2.val){
boolean check1 = flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right);
boolean check2 = flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left);
boolean c = check1 || check2;
return c;
}else return false;
}
Time O(min(n1, n2))
Space O(min(h1, h2))
[Binary Tree Con.][SubTree/Leaves]
#222 Count Complete Tree Nodes
- BFS
public int countNodes(TreeNode root) {
if(root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
int res = 0;
while(!q.isEmpty()){
int size = q.size();
res += size;
for(int i = 0; i < size; i++){
TreeNode cur = q.poll();
if(cur.left != null) q.add(cur.left);
if(cur.right != null) q.add(cur.right);
}
}
return res;
}
Time O(n)
Space O(n)
- Sol1 Recursive
public int countNodes(TreeNode root) {
if(root == null) return 0;
int left_height = help(root.left);
int right_height = help(root.right);
if(left_height == right_height){
return left_height == 0? 1 : (1 << left_height) - 1 + 1 + countNodes(root.right);
}else{
return right_height == 0? countNodes(root.left) + 1:(1 << right_height) - 1 + 1 + countNodes(root.left);
}
}
public int help(TreeNode root){
int height = 0;
while(root != null){
height++;
root = root.left;
}
return height;
}
Time O(log(n))
Space O(log(n))
#508 Most Frequent Subtree Sum
- Sol1 HashMap
int max_count = 0;
Map<Integer, Integer> sum_hash;
Map<Integer, ArrayList<Integer>> count_hash;
public int[] findFrequentTreeSum(TreeNode root) {
sum_hash = new HashMap<>(); //<sum, count>
help(root);
ArrayList<Integer> re = new ArrayList<>();
if(max_count == 0) return new int[0];
for (Map.Entry<Integer, Integer> entry : sum_hash.entrySet()) {
if(max_count == entry.getValue()){
re.add(entry.getKey());
}
}
int[] res = new int[re.size()];
int i = 0;
for(Integer a: re){
res[i++] = a;
}
return res;
}
public int help(TreeNode root){
if(root == null) return 0;
int sum = help(root.left) + help(root.right) + root.val;
if(sum_hash.containsKey(sum)){
sum_hash.put(sum, sum_hash.get(sum)+1);
}else{
sum_hash.put(sum, 1);
}
if(sum_hash.get(sum) > max_count) max_count = sum_hash.get(sum);
return sum;
}
#993 Cousins in Binary Tree
- Sol1 DFS
TreeNode parent = null;
public boolean isCousins(TreeNode root, int x, int y) {
int find_x = find(root, x, 1, parent);
TreeNode parent_x = null;
if(parent != null) parent_x = parent;
parent = null;
int find_y = find(root, y, 1, parent);
TreeNode parent_y = null;
if(parent != null) parent_y = parent;
return find_x == find_y && parent_x != parent_y;
}
public int find(TreeNode root, int cur, int level, TreeNode parent){
if(root == null) return 0;
if(root.val == cur){
this.parent = parent;
return level;
}
int ld = find(root.left, cur, level+1, root);
if(ld != 0) return ld;
return find(root.right, cur, level + 1, root);
}
Time O(n)
Space O(h)
[Binary Tree Con.][Other BT]
#116 Populating Next Right Pointers in Each Node
-
Sol1 Pre order
Recursive
public Node connect(Node root) {
if(root == null || root.left == null) return root;
root.left.next = root.right;
if(root.next!=null)
root.right.next = root.next.left;
connect(root.left);
connect(root.right);
return root;
}
Time O(n)
Space O(1)
- Sol2 Level Order
public Node connect(Node root) {
if(root==null) return root;
Queue<Node> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()){
int size = q.size();
Node previous = null;
for(int i = 0; i < size; i++){
Node cur = q.poll();
if(previous != null) previous.next = cur;
previous = cur;
if(cur.left!=null) q.offer(cur.left);
if(cur.right!=null) q.offer(cur.right);
}
}
return root;
}
Time O(n)
Space O(n)
#117 Populating Next Right Pointers in Each Node II
- Sol1 Level Order
public Node connect(Node root) {
if(root==null) return root;
Queue<Node> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()){
int size = q.size();
Node previous = null;
for(int i = 0; i < size; i++){
Node cur = q.poll();
if(previous != null) previous.next = cur;
previous = cur;
if(cur.left!=null) q.offer(cur.left);
if(cur.right!=null) q.offer(cur.right);
}
}
return root;
}
Time O(n)
Space O(n)
- Sol2 Dummy node
public Node connect(Node root) {
Node dummy = new Node();
Node pre = dummy;
Node cur = root;
while(cur != null){
if(cur.left != null){
pre.next = cur.left;
pre = pre.next;
}
if(cur.right != null){
pre.next = cur.right;
pre = pre.next;
}
cur = cur.next;
if(cur == null){
pre = dummy;
cur = pre.next;
dummy.next = null; //keep dummy is new Node();
}
}
return root;
}
Time O(n)
Space O(1)
#236 Lowest Common Ancestor of a Binary Tree
-
Sol1 Recursive
DFS搜索p与q，记录每个node点的left，right，mid。mid为node是否为p，q其中一个。left为p或q是否存在左分支上，right同理。
TreeNode res;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
res = null;
help(root, p, q);
return res;
}
public boolean help(TreeNode root, TreeNode p, TreeNode q){
if(root == null) return false;
int left = help(root.left, p, q) ? 1 : 0;
int right = help(root.right, p, q) ? 1 : 0;
int mid = (root.val == p.val || root.val == q.val) ? 1 : 0;
if(left + right + mid >=2){
res = root;
}
return left + right + mid > 0;
}
Time O(n)
Space O(n)
-
Sol2 Iterative
map存储node的parent，之后backtrack查找共同的ancestor
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
Map<TreeNode,TreeNode> map = new HashMap<>(); //node, parent
Stack<TreeNode> s = new Stack<>();
s.push(root);
map.put(root, null);
while(!map.containsKey(p) || !map.containsKey(q)){
TreeNode cur = s.pop();
if(cur.left != null){
map.put(cur.left, cur);
s.push(cur.left);
}
if(cur.right != null){
map.put(cur.right, cur);
s.push(cur.right);
}
}
Set<TreeNode> back = new HashSet<>();
while(p != null){
back.add(p);
p = map.get(p);
}
while(!back.contains(q)){
q = map.get(q);
}
return q;
}
Time O(n)
Space O(n)
#297 Serialize and Deserialize Binary Tree
可以与449. Serialize and Deserialize BST比较做
- Sol1 Recursive
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
ser_help(sb, root);
return sb.toString();
}
public void ser_help(StringBuilder sb, TreeNode root){
if(root == null){
sb.append("*").append(",");
return;
}
sb.append(root.val).append(",");
ser_help(sb, root.left);
ser_help(sb, root.right);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Queue<String> q = new LinkedList<>();
q.addAll(Arrays.asList(data.split(",")));
return des_help(q);
}
public TreeNode des_help(Queue<String> q){
String cur = q.poll();
if(cur.equals("*")) return null;
TreeNode root = new TreeNode(Integer.valueOf(cur));
root.left = des_help(q);
root.right = des_help(q);
return root;
}
[BST(补充)]
#235 Lowest Common Ancestor of a Binary Search Tree
-
Sol1 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);
}
if(p.val < root.val && q.val < root.val){
return lowestCommonAncestor(root.left, p, q);
}
return root;
}
Time O(n)
Space O(n)
- Sol2 Iterative
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int p_val = p.val, q_val = q.val;
TreeNode cur = root;
while(cur != null){
if(cur.val < p_val && cur.val < q_val) cur = cur.right;
else if(cur.val > p_val && cur.val > q_val) cur = cur.left;
else return cur;
}
return null;
}
Time O(n)
Space O(1) 不需要stack因为不需要backtrack
[Others]
#337 House Robber III
- Sol1 DFS
public int rob(TreeNode root) {
if(root == null) return 0;
int[] res = new int[2];
res = help(root);
return Math.max(res[0], res[1]);
}
public int[] help(TreeNode root){
int[] res = new int[2];
if(root == null){
res[0] = 0;
res[1] = 0;
return res;
}
int[] left = help(root.left);
int[] right = help(root.right);
res[0] = root.val + left[1] + right[1];
res[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return res;
}
#834 Sum of Distances in Tree
Hard
-
Sol Subtree + DFS
List<Set>存树结构，pre_order遍历更新count与res，得到root的正确res与每个点的count值，post_order更新所有所有点的res
List<Set<Integer>> tree;
int N;
int[] res, count;
public int[] sumOfDistancesInTree(int N, int[][] edges) {
tree = new ArrayList<>();
this.N = N;
res = new int[N];
count = new int[N];
Arrays.fill(count, 1);
for(int i = 0; i < N; i++){
tree.add(new HashSet<>());
}
for(int[] edge: edges){
tree.get(edge[0]).add(edge[1]);
tree.get(edge[1]).add(edge[0]);
}
dfs(0, -1);
dfs2(0, -1);
return res;
}
public void dfs(int node, int parent){
for(int child: tree.get(node)){
if(child != parent){
dfs(child, node);
count[node] += count[child];
res[node] += res[child] + count[child];
}
}
}
public void dfs2(int node, int parent){
for(int child: tree.get(node)){
if(child != parent){
res[child] = res[node] - count[child] + N - count[child];
dfs2(child, node);
}
}
}
#310 Minimum Height Trees
-
Sol BFS
List<Set>存树结构，记录每个点的in degree
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Set<Integer>> tree = new ArrayList<>();
List<Integer> res = new ArrayList<>();
if (edges.length == 0) {
res.add(0);
return res;
}
int[] indegree = new int[n];
Queue<Integer> q = new LinkedList<>();
for(int i = 0; i < n; i++)
{
tree.add(new HashSet<>());
}
for(int[] edge: edges){
tree.get(edge[0]).add(edge[1]);
tree.get(edge[1]).add(edge[0]);
}
for(int i = 0; i < n; i++){
indegree[i] = tree.get(i).size();
if(indegree[i] == 1) q.add(i);
}
int count = 0;
while(!q.isEmpty()){
int size = q.size();
count += size;
for(int i = 0; i < size; i++){
int cur = q.poll();
indegree[cur]--;
if(count == n) {
res.add(cur);
}
for(Integer node: tree.get(cur)){
if(indegree[node]!=0){
indegree[node]--;
if(indegree[node] == 1) q.add(node);
}
}
}
}
return res;
}
** 558* Quad Tree Intersection
- Sol Recursive
public Node intersect(Node quadTree1, Node quadTree2) {
if(quadTree1.isLeaf){
return quadTree1.val ? quadTree1 : quadTree2;
}else if(quadTree2.isLeaf){
return quadTree2.val ? quadTree2 : quadTree1;
}
Node TL = intersect(quadTree1.topLeft, quadTree2.topLeft);
Node TR = intersect(quadTree1.topRight, quadTree2.topRight);
Node BL = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
Node BR = intersect(quadTree1.bottomRight, quadTree2.bottomRight);
if(TL.isLeaf && TR.isLeaf && BL.isLeaf && BR.isLeaf && TL.val == TR.val && TL.val == BL.val && TL.val == BR.val)
return new Node(TL.val, true, null, null, null, null);
Node res = new Node(false, false, TL, TR, BL, BR);
return res;
}
