题目：
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
将两棵树的首先条件判断后，递归代码简单，直接循环判断两棵树对应孩子是否相同；非递归借助栈将节点入栈保存，出栈比较。相比较过程也是可以理解的，代码如下：
//递归 /* class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if(p == NULL && q == NULL) return true; if((p == NULL && q != NULL) || (p != NULL && q== NULL)) return false; if(p->val != q->val) return false; else return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right); } }; */ //非递归 class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { stack<TreeNode*> pnode; stack<TreeNode*> qnode; if(p == NULL && q == NULL) return true; if((p == NULL && q != NULL) || (p != NULL && q== NULL)) return false; if(p->val != q->val) return false; else { pnode.push(p); qnode.push(q); } while(!pnode.empty() && !qnode.empty()) { p = pnode.top(); q = qnode.top(); pnode.pop(); qnode.pop(); if(q == NULL&&p == NULL) continue;//如果两棵树当前的结点都为空，不做任何，跳到下一步，继续判断； if((p==NULL&&q!=NULL)||(p!=NULL&&q==NULL)||(p->val != q->val)) return false; pnode.push(p->left); //相同顺序分支孩子入栈 pnode.push(p->right); qnode.push(q->left); qnode.push(q->right); } if(pnode.empty() && qnode.empty()) return true; return false; } };
