https://leetcode.com/problems/same-tree/

题目：

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.

思路：  DFS

AC代码：

1.递归

1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     bool isSameTree(TreeNode* p, TreeNode* q) {13         if (p==NULL && q==NULL)14             return true;15         else if(p!=NULL&&q!=NULL){16         bool ju;17         if(p->val==q->val)18             ju=true;19         else20             return false;21         if (p->left==NULL && q->left==NULL)22             ;23         else if(p->left!=NULL && q->left!=NULL)24             ju=ju&&isSameTree(p->left,q->left);25         else26             return false;27         if (p->right==NULL && q->right==NULL)28             ;29         else if(p->right!=NULL && q->right!=NULL)30             ju=ju&&isSameTree(p->right,q->right);31         else32             return false;33         return ju;34         }35         else36             return false;37     }38 };

2.非递归

1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     bool isSameTree(TreeNode* p, TreeNode* q) {13         if(p==NULL&&q==NULL)14             return true;15         else if(p!=NULL && q!=NULL){16             stack
     
       ms1,ms2;17             ms1.push(p);18             ms2.push(q);19             TreeNode* p1,*q1;20             while(!ms1.empty()){21                 p1=ms1.top();22                 q1=ms2.top();23                 if(p1->val!=q1->val)24                     return false;25                 else{26                     ms1.pop();27                     ms2.pop();28                     if(p1->right==NULL&&q1->right==NULL)29                         ;30                     else if(p1->right!=NULL&&q1->right!=NULL){31                         ms1.push(p1->right);32                         ms2.push(q1->right);33                     }34                     else35                         return false;36                     if(p1->left==NULL&&q1->left==NULL)37                         ;38                     else if(p1->left!=NULL&&q1->left!=NULL){39                         ms1.push(p1->left);40                         ms2.push(q1->left);41                     }42                     else43                         return false;44                     }45                 }46                 return true;47             }48         else 49             return false;50     }51 };