题目：
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.
代码：
/** * Definition for a binary tree node. * 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) { if ( !p && !q ) return true; stack sta_p,sta_q; if (p) sta_p.push(p); if (q) sta_q.push(q); while ( !sta_p.empty() && !sta_q.empty() ){ TreeNode * tmp_p = sta_p.top(); sta_p.pop(); TreeNode * tmp_q = sta_q.top(); sta_q.pop(); // node val if ( tmp_p->val==tmp_q->val ){ // right child if ( tmp_p->right && tmp_q->right ){ sta_p.push(tmp_p->right); sta_q.push(tmp_q->right); } else if ( !tmp_p->right && !tmp_q->right ) {} else{ return false; } // left child if ( tmp_p->left && tmp_q->left ){ sta_p.push(tmp_p->left); sta_q.push(tmp_q->left); } else if ( !tmp_p->left && !tmp_q->left ) {} else{ return false; } } else { return false; } } return sta_p.empty() && sta_q.empty(); }}; tips：
二叉树先序遍历。
1. 比较节点val
2. 比较节点right child
3. 比较节点left child
========================
学习了一个更简洁版的代码，主要简洁的地方是入栈时候不需要判断为NULL。
代码：
/** * Definition for a binary tree node. * 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) { stack sta_p,sta_q; sta_p.push(p); sta_q.push(q); while ( !sta_p.empty() && !sta_q.empty() ) { p = sta_p.top(); sta_p.pop(); q = sta_q.top(); sta_q.pop(); if ( !q && !p ) continue; if ( !q || !p ) return false; if ( p->val!=q->val ) return false; sta_p.push(p->right); sta_p.push(p->left); sta_q.push(q->right); sta_q.push(q->left); } return sta_p.empty() && sta_q.empty(); }}; ==============================================
第二次过这道题，第一次没有AC：有个思维陷阱，如果线序遍历输出的顺序相同，两棵树不一定完全相等。改了一次后AC了。
/** * Definition for a binary tree node. * 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) { stack sta1; if (p) sta1.push(p); stack sta2; if (q) sta2.push(q); while ( !sta1.empty() && !sta2.empty() ) { TreeNode* n1 = sta1.top(); sta1.pop(); TreeNode* n2 = sta2.top(); sta2.pop(); if ( n1->val != n2->val ) return false; // right child if ( n1->right && n1->right ) { sta1.push(n1->right); sta2.push(n2->right); } else if ( !n1->right && !n2->right ) {} else { return false; } // left child if ( n1->left && n1->left ) { sta1.push(n1->left); sta2.push(n2->left); } else if ( !n1->left && !n2->left ) {} else { return false; } } return sta1.empty() && sta2.empty(); }}; 再补上一个递归版的。
/** * Definition for a binary tree node. * 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) { if ( p && q ) { if ( p->val==q->val ) { return Solution::isSameTree(p->left, q->left) && Solution::isSameTree(p->right, q->right); } else { return false; } } else if ( !p && !q ) { return true; } else { return false; } }};