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)

100 - Same Tree

Question

Algorithm

Code

All Problems

All Solutions