判断两颗二叉树是否相同

1. LeetCode 100. Same Tree

2. 描述：

给定两个二叉树，判断这两棵树是否相同（包括树的结构和节点的值）

3. 解决方案 1 :

class Solution {
public:
	bool isSameTree(TreeNode* p, TreeNode* q) {
		if(p == nullptr && q == nullptr){
			return true;
		}else if(p == nullptr || q == nullptr){
			return false;
		}else if(p->val != q->val){
			return false;
		}else{
			return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
		}
	}
};

4. 解决方案 2：

bool isSameTree(TreeNode* p, TreeNode* q) {
    if(p == nullptr || q == nullptr){
        return p == q;
    }
    return (p->val == q->val) && 
        isSameTree(p->left, q->left) && 
        isSameTree(p->right, q->right); 
}

5. 解决方案3：迭代非递归

bool isSameTree(TreeNode* p, TreeNode* q) {
    stack<TreeNode*> stack1;
    stack<TreeNode*> stack2;
    
    if(p != nullptr) stack1.push(p);
    if(q != nullptr) stack2.push(q);
    
    while(!stack1.empty() && !stack2.empty()){
        TreeNode* p1 = stack1.top();
        stack1.pop();
        TreeNode* q1 = stack2.top();
        stack2.pop();
        
        if(p1->val != q1->val) return false;
        
        if(p1->left != nullptr) stack1.push(p1->left);
        if(q1->left != nullptr) stack2.push(q1->left);
        if(stack1.size() != stack2.size()) return false;
        
        if(p1->right != nullptr) stack1.push(p1->right);
        if(q1->right != nullptr) stack2.push(q1->right);
        if(stack1.size() != stack2.size()) return false;
    }
    return stack1.size() == stack2.size();
}