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.
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
The description was taken from https://leetcode.com/problems/same-tree/.
#Recursive#O(N) Time, O(log(N)) Space for Balanced, O(N) for Unbalanced Treeclass Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: if p is None and q is None: return True if p is None or q is None: return False if p.val != q.val: return False return self.isSameTree(p.left, q.left) and \ self.isSameTree(p.right, q.right)#Iterative#O(N) Time, O(log(N)) Space for Balanced, O(N) for Unbalanced Treeclass Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: stack = [(p,q)] while stack : x,y = stack.pop() if x is None and y is None: continue if x is None or y is None: return False if x.val != y.val: return False else: stack.append((x.left,y.left)) stack.append((x.right,y.right)) return True
If we are considering two trees to be the same, we would need to have in mind what would make them different. These two things would be different heights and different values.
Different values are straightforward, if one root is five and the other is four then the trees are different.
Different heights from the bottom is the other invalidation. If one tree has a subtree with a child node and the other tree doesn't, then that means that the first subtree's child node has a height of one while the other has a height of zero, making them different.
We can solve this problem by checking for mismatched values in the tree roots, and then recursing the isSameTree function on the left and right children until we reach null nodes.
If both nodes are none, they still match so we will return true.
if p is None and q is None: return True
If only one of the nodes is none, they don't match so we will return false.
if p is None or q is None: return False
If the values of the nodes aren't equal, they don't match so we will return false.
if p.val != q.val: return False
If we have checked the values of the nodes and they are the same, we will do the same thing on the left and right children.
return self.isSameTree(p.left, q.left) and \ self.isSameTree(p.right, q.right)
If all recursive calls have returned true, the trees are the same.
The only difference we have to make here is swapping out the call stack for a loop and iterative stack. This is typically how simple it is to convert a preorder or inorder recursive traversal to an iterative one.
We can solve this problem by checking for mismatched values in the tree roots by pushing them into a stack, and if the nodes match up then we will push the node's children onto the stack and continue.
We will start by initializing a stack and pushing both roots onto it.
stack = [(p,q)]
Then, we will create a loop that will run while the stack still has nodes.
while stack :
During each iteration, we will pop two nodes off of the stack and set two variables, x and y to these nodes.
x,y = stack.pop()
If both nodes are none, they still match so we will continue.
if x is None and y is None: continue
If only one of the nodes is none, they don't match so we will return false.
if x is None or y is None: return False
If the values of the nodes aren't equal, they don't match so we will return false.
if x.val != y.val: return False
Otherwise, if both node values are equal then we will push both of the nodes' children onto the stack and do the same thing.
stack.append((x.left,y.left)) stack.append((x.right,y.right))
If we get an empty stack, then that means all of the nodes have the same order and values and the trees are the same so we will return true.
return True