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)
    
    

All Problems

All Solutions