Problem:
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
Solution: Recursion
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { // Both are emtry: same if (!p && !q) return true; // One is emtry: not the Same if (!p || !q) return false; // Both are not emptry, compare the root value if (p->val != q->val) return false; // Compare left-subtree and right-subtree recursively. return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); } }; |
Java
|
1 2 3 4 5 6 7 8 |
// Author: Huahua class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) return true; if (p == null || q == null) return false; return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 |
""" Author: Huahua """ class Solution: def isSameTree(self, p, q): if not p and not q: return True if not p or not q: return False return all((p.val == q.val, self.isSameTree(p.left, q.left), self.isSameTree(p.right, q.right))) |