1.题目描述

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.

2.解法分析

与上一篇文章“Symmetric Tree”一样的思路，只是要证明两棵树完全一样，需对两棵树进行一模一样的遍历。当然最好是深度搜索。

/**

* Definition for binary tree

* struct TreeNode {

*     int val;

*     TreeNode *left;

*     TreeNode *right;

*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

*/

class Solution {

public:

bool isSameTree(TreeNode *p, TreeNode *q) {

// Start typing your C/C++ solution below

// DO NOT write int main() function

vector
           
             vp;
           

vector
           
             vq;
           

TreeNode *curp= p;

TreeNode *curq =q;

while(curp||!vp.empty())

{

while(curp)

{

if(!curq)return false;

if(curp->val!=curq->val)return false;

vp.push_back(curp);

vq.push_back(curq);

curp=curp->left;

curq=curq->left;

}

if(!vp.empty())

{

if(curp)return false;

curp=vp.back();vp.pop_back();curp=curp->right;

curq=vq.back();vq.pop_back();curq=curq->right;

}

}

if((vp.empty()&&!vq.empty())||(!vp.empty()&&vq.empty()))return false;

if((curp&&!curp)||(!curp&&curq))return false;

return true;

}

};