1.2 Same Tree

Description

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.

Method

Tree problem : recursive method or non-recursive recursive non- recursive : stack

Time and Space Complexity

o(n)

Code

for recursive:

public class Solution {

public boolean isSameTree(TreeNode p, TreeNode q) {
      if (p == null || q == null){
          return p == q;
      } 
      if (p.val != q.val){
          return false;
      } 
      return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

}

for non-recursive:

public class Solution {

public boolean isSameTree(TreeNode p, TreeNode q){

       Stack<TreeNode> stack = new Stack<TreeNode>();
       stack.push(p);
       stack.push(q);
       while (!stack.isEmpty()){
              TreeNode first = stack.pop();
              TreeNode second = stack.pop();
              if (first == null || second == null){
                  if (first == second){
                      continue;
                  } else {
                      return false;
                  }
              } 
              if (first.val != second.val){
                  return false;
              }
              stack.push(first.left);
              stack.push(second.left);
              stack.push(first.right);
              stack.push(second.right);
       }
       return true;
}

}