You can cut down space complexity to O(N) or O(M) if you use a queue and a boolean variable to detect when the trees are dissimilar (we'll call it leafSimilar, intiialized to true) Run a post-order traversal on tree 1, add all leaf nodes to queue. Run a post-order traversal on tree 2, remove from the queue if current node value matches element at the front. If not, set leafSimilar to false and return. If length of the queue is 0 after traversal on tree 2 and the leafSimilar variable is true, they are leaf-similar.
You can indeed make it in O(h1+h2) space complexity: You change the dfs into an iterative approach with stacks. (You push each node to the stack, first the right and then the left element). When you reach a leaf with root 1, you do the same with root2. Then you compare the values and go on.
This was a pretty easy one. I wonder if it can be solved without creating extra space for arrays. Maybe someway we could traverse both trees together, and return false on the fly.
Wrote something almost exactly as NeetCode on my first try. Came up with a way without storing the array after some optimization. The trick was to add left and right together and return a list with only the root's value if that list is empty. def dfs(root): if not root: return [] temp = dfs(root.left) + dfs(root.right) return temp or [root.val] return dfs(root1) == dfs(root2)
@@HardcoreJapanese isn’t this still O(N) space complexity? If we consider the worst case of a full binary tree of N nodes, we would have temp = (N+1)/2 leaves which would be O(N) space. If you’re comparing dfs(root1) == dfs(root2) that will always be O(N)
Here's a way (in Java) - without extra space for arrays - basically recursion manually public boolean leafSimilar(TreeNode root1, TreeNode root2) { Stack stack1 = new Stack(); Stack stack2 = new Stack(); stack1.push(root1); stack2.push(root2);
while (!stack1.isEmpty() && !stack2.isEmpty()) { if (dfs(stack1) != dfs(stack2)) { return false; } }
return stack1.isEmpty() && stack2.isEmpty(); } private int dfs(Stack stack) { while (true) { TreeNode node = stack.pop(); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } if (node.left == null && node.right == null) { return node.val; } } }
I implemented this exact method but with lists instead of arrays on my first attempt. However, I wanted to reduce the memory usage and increase the performance of my code so I implemented this idea: One recursive function stores all the leaves of the first BST inside a FIFO (First in First out) data structure and the second recursive function removes its elements one by one while comparing them with the leaves of the second BST. This worked out pretty well but when I tried to submit the code it failed. Leetcode says when you input [1] [1], my code returns false when it's suppose to return true. However when I run my code on my compiler with the exact same input it returned true. I read and run my code over and over again and there doesn't seem to be any issues with it but for some reason it doesn't work when I try to submit the code.
Can you make a video for what kinds of projects can be included in Resume for freshers and experienced people. I see recruiters ask experienced people to talk about their own created projects. If you have already created a video on this, then I might have missed it. But if you give your views on this that would be great.
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool: arr1,arr2=[],[] def helper(root,arr): if root: if root.left ==None and root.right==None: arr.append(root.val) helper(root.left,arr) helper(root.right,arr) helper(root1,arr1) helper(root2,arr2)
You possibly achieve constant space by iterating each tree's next leaf node, instead of storing all leaf nodes in a list for each tree. Nonetheless I like the simplify and elegance of this solution.
my code : class Solution: def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool: ans=[] def dfs(root): if not root:return if not root.left and not root.right: ans.append(root.val) print(root.val) else: dfs(root.left) dfs(root.right) return dfs(root1) half=len(ans) dfs(root2) print(ans[0:half],ans[half:]) return ans[0:half]==ans[half:]
You can cut down space complexity to O(N) or O(M) if you use a queue and a boolean variable to detect when the trees are dissimilar (we'll call it leafSimilar, intiialized to true)
Run a post-order traversal on tree 1, add all leaf nodes to queue.
Run a post-order traversal on tree 2, remove from the queue if current node value matches element at the front. If not, set leafSimilar to false and return.
If length of the queue is 0 after traversal on tree 2 and the leafSimilar variable is true, they are leaf-similar.
Please upload leetcode contests videos @neetcode
Great explanation as always! Thank you !!!
You can indeed make it in O(h1+h2) space complexity: You change the dfs into an iterative approach with stacks. (You push each node to the stack, first the right and then the left element). When you reach a leaf with root 1, you do the same with root2. Then you compare the values and go on.
You can do it in constant space, I used generators in python to iterate over the leaves
This was a pretty easy one. I wonder if it can be solved without creating extra space for arrays. Maybe someway we could traverse both trees together, and return false on the fly.
Wrote something almost exactly as NeetCode on my first try. Came up with a way without storing the array after some optimization. The trick was to add left and right together and return a list with only the root's value if that list is empty.
def dfs(root):
if not root:
return []
temp = dfs(root.left) + dfs(root.right)
return temp or [root.val]
return dfs(root1) == dfs(root2)
@@HardcoreJapanese still recursion uses stack so you are not saving any memory there
@@shreehari2589 That's true. I didn't think about that.
@@HardcoreJapanese isn’t this still O(N) space complexity? If we consider the worst case of a full binary tree of N nodes, we would have temp = (N+1)/2 leaves which would be O(N) space. If you’re comparing dfs(root1) == dfs(root2) that will always be O(N)
Here's a way (in Java) - without extra space for arrays - basically recursion manually
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
Stack stack1 = new Stack();
Stack stack2 = new Stack();
stack1.push(root1);
stack2.push(root2);
while (!stack1.isEmpty() && !stack2.isEmpty()) {
if (dfs(stack1) != dfs(stack2)) {
return false;
}
}
return stack1.isEmpty() && stack2.isEmpty();
}
private int dfs(Stack stack) {
while (true) {
TreeNode node = stack.pop();
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
if (node.left == null && node.right == null) {
return node.val;
}
}
}
I implemented this exact method but with lists instead of arrays on my first attempt. However, I wanted to reduce the memory usage and increase the performance of my code so I implemented this idea:
One recursive function stores all the leaves of the first BST inside a FIFO (First in First out) data structure and the second recursive function removes its elements one by one while comparing them with the leaves of the second BST.
This worked out pretty well but when I tried to submit the code it failed. Leetcode says when you input [1] [1], my code returns false when it's suppose to return true. However when I run my code on my compiler with the exact same input it returned true.
I read and run my code over and over again and there doesn't seem to be any issues with it but for some reason it doesn't work when I try to submit the code.
Can you make a video for what kinds of projects can be included in Resume for freshers and experienced people.
I see recruiters ask experienced people to talk about their own created projects.
If you have already created a video on this, then I might have missed it. But if you give your views on this that would be great.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
arr1,arr2=[],[]
def helper(root,arr):
if root:
if root.left ==None and root.right==None:
arr.append(root.val)
helper(root.left,arr)
helper(root.right,arr)
helper(root1,arr1)
helper(root2,arr2)
return arr1==arr2
Yaay, I wrote exactly the same code
whoa i came up with the same solution as yours for the first time. i usually come up with a less optimal solution than yours. thx for the vids!
nicce Beats
You possibly achieve constant space by iterating each tree's next leaf node, instead of storing all leaf nodes in a list for each tree.
Nonetheless I like the simplify and elegance of this solution.
class Solution {
List list1 = new ArrayList();
List list2 = new ArrayList();
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
dfs(root1,list1);
dfs(root2,list2);
return list1.equals(list2);
}
void dfs(TreeNode root, List list) {
if ( root == null ) return;
if ( root.left == null && root.right == null ) {
list.add(root.val);
return;
}
dfs(root.left,list);
dfs(root.right,list);
}
}
why do you have int i in your dis method, it does nothing at all
@@letmeseeu good catch, that was leftover code from my first attempt at the problem
@NeetCodeIO: Mr Neet saves the day again. Thanks.
apparently i solved this myself with your exact same solution 2 months ago
Its not a neetcode video if there isn't a single error in the code 🙃
I'm so cooked
fuck my life
my code :
class Solution:
def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
ans=[]
def dfs(root):
if not root:return
if not root.left and not root.right:
ans.append(root.val)
print(root.val)
else:
dfs(root.left)
dfs(root.right)
return
dfs(root1)
half=len(ans)
dfs(root2)
print(ans[0:half],ans[half:])
return ans[0:half]==ans[half:]