Question
Formatted question description: https://leetcode.ca/all/100.html
100 Same Tree
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
@tag-tree
Algorithm
Depth first search DFS to recurse.
Code
Java
-
public class Same_Tree { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution_iteration { public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null) { return q == null; } if (q == null) { return p == null; } Stack<TreeNode> sk1 = new Stack<TreeNode>(); Stack<TreeNode> sk2 = new Stack<TreeNode>(); sk1.push(p); sk2.push(q); while (!sk1.isEmpty() && !sk2.isEmpty()) { TreeNode current1 = sk1.pop(); TreeNode current2 = sk2.pop(); if (current1 == null && current2 == null) { continue; // @note: missed both null check } else if (current1 == null && current2 != null) { return false; } else if (current1 != null && current2 == null) { return false; } else if (current1.val != current2.val) { return false; } sk1.push(current1.left); sk2.push(current2.left); sk1.push(current1.right); sk2.push(current2.right); } // final check if (!sk1.isEmpty() || !sk2.isEmpty()) { return false; } return true; } } public class Solution_recursion { public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null) { return q == null; } if (q == null) { return p == null; } if (p.val != q.val) { return false; } return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } } }
-
// OJ: https://leetcode.com/problems/same-tree/ // Time: O(N) // Space: O(H) class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { return (!p && !q) || (p && q && p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right)); } };
-
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def isSameTree(self, p, q): """ :type p: TreeNode :type q: TreeNode :rtype: bool """ if not p or not q: return p == q return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)