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.

Solution1：递归对比

Time Complexity: O(N) Space Complexity: O(N) 递归缓存

Solution2：前序遍历对比

思路： 除了前序的元素值，前序的结构也需要check，是否同为Null或同存在，通过push后(非null) check stack_p.size() != stack_q.size()
Time Complexity: O(N) Space Complexity: O(N)

Solution1 Code：

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

Solution2 Code：

class Solution2 {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Stack<TreeNode> stack_p = new Stack<> ();       
        Stack<TreeNode> stack_q = new Stack<> ();
        if (p != null) stack_p.push( p ) ;
        if (q != null) stack_q.push( q ) ;
        while (!stack_p.isEmpty() && !stack_q.isEmpty()) {
            TreeNode pn = stack_p.pop() ;
            TreeNode qn = stack_q.pop() ;           
            if (pn.val != qn.val) return false ;
            if (pn.right != null) stack_p.push(pn.right) ;
            if (qn.right != null) stack_q.push(qn.right) ;
            if (stack_p.size() != stack_q.size()) return false ;
            if (pn.left != null) stack_p.push(pn.left) ;                         
            if (qn.left != null) stack_q.push(qn.left) ;
            if (stack_p.size() != stack_q.size()) return false ;
         }           
         return stack_p.size() == stack_q.size() ;   
    }
}