Same Tree
Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Example 1:
Input: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
Output: true
Example 2:
Input: 1 1
/ \
2 2
[1,2], [1,null,2]
Output: false
Example 3:
Input: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
Output: false
Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) return true;
if((p == null && q != null) || (p != null && q ==null))
return false;
if(p.val == q.val){
if(isNode(p) && isNode(q)){
return true;
}
else if((p.left == null && q.left != null) ||
(p.left != null&& q.left ==null) ||
(p.right == null && p.right != null) ||
(p.right != null && p.right == null)
){
return false;
}
else{
return isSameTree(p.left,q.left) &&
isSameTree(p.right,q.right);
}
}
else{
return false;
}
}
private boolean isNode(TreeNode node){
if(node.left == null && node.right == null){
return true;
}
else return false;
}
}
Approach 1: Recursion Intuition
The simplest strategy here is to use recursion. Check if p and q nodes are not None, and their values are equal. If all checks are OK, do the same for the child nodes recursively.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// p and q are both null
if (p == null && q == null) return true;
// one of p and q is null
if (q == null || p == null) return false;
if (p.val != q.val) return false;
return isSameTree(p.right, q.right) &&
isSameTree(p.left, q.left);
}
}
Complexity Analysis
-
Time complexity : \mathcal{O}(N)O(N), where N is a number of nodes in the tree, since one visits each node exactly once.
-
Space complexity : \mathcal{O}(\log(N))O(log(N)) in the best case of completely balanced tree and \mathcal{O}(N)O(N) in the worst case of completely unbalanced tree, to keep a recursion stack.
Approach 2: Iteration Intuition
Start from the root and then at each iteration pop the current node out of the deque. Then do the same checks as in the approach 1 :
p and p are not None,
p.val is equal to q.val,
and if checks are OK, push the child nodes.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public boolean check(TreeNode p, TreeNode q) {
// p and q are null
if (p == null && q == null) return true;
// one of p and q is null
if (q == null || p == null) return false;
if (p.val != q.val) return false;
return true;
}
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (!check(p, q)) return false;
// init deques
ArrayDeque<TreeNode> deqP = new ArrayDeque<TreeNode>();
ArrayDeque<TreeNode> deqQ = new ArrayDeque<TreeNode>();
deqP.addLast(p);
deqQ.addLast(q);
while (!deqP.isEmpty()) {
p = deqP.removeFirst();
q = deqQ.removeFirst();
if (!check(p, q)) return false;
if (p != null) {
// in Java nulls are not allowed in Deque
if (!check(p.left, q.left)) return false;
if (p.left != null) {
deqP.addLast(p.left);
deqQ.addLast(q.left);
}
if (!check(p.right, q.right)) return false;
if (p.right != null) {
deqP.addLast(p.right);
deqQ.addLast(q.right);
}
}
}
return true;
}
}
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.
1
2
3
4
5
6
7
8
9
10
11
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
Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private LinkedList<Integer> myLinkedList = new LinkedList<>();
public TreeNode convertBST(TreeNode root) {
if(root == null){
return null;
}
getGreaterValList(root);
Queue<TreeNode> myQueue = new LinkedList<>();
myQueue.add(root);
while(!myQueue.isEmpty()){
TreeNode tmp = myQueue.poll();
int sum = 0;
for(int val : myLinkedList){
if(tmp.val < val){
sum += val;
}
}
tmp.val += sum;
if(tmp.left != null){
myQueue.add(tmp.left);
}
if(tmp.right != null){
myQueue.add(tmp.right);
}
}
return root;
}
void getGreaterValList(TreeNode root){
if(root != null){
myLinkedList.add(root.val);
}
if(root.left != null){
getGreaterValList(root.left);
}
if(root.right != null){
getGreaterValList(root.right);
}
}
}
Approach #1 Recursion [Accepted] Intuition
One way to perform a reverse in-order traversal is via recursion. By using the call stack to return to previous nodes, we can easily visit the nodes in reverse order.
Algorithm
For the recursive approach, we maintain some minor “global” state so each recursive call can access and modify the current total sum. Essentially, we ensure that the current node exists, recurse on the right subtree, visit the current node by updating its value and the total sum, and finally recurse on the left subtree. If we know that recursing on root.right properly updates the right subtree and that recursing on root.left properly updates the left subtree, then we are guaranteed to update all nodes with larger values before the current node and all nodes with smaller values after.
