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) {} };解题思路： 要判断2个二叉树是否一样，需要遍历树的所有节点，所以可以使用深度优先算法(DFS)来解决。 竟然要用到DFS，那么可以用到stack，那么stack里面的应该存放什么。我的想法是存放一种结构体，这个结构体包含了2个树相同位置的节点的指针。可以发现题目给出的TreeNode其实已经满足了要求，我们可以用TreeNode的left来指向第一个二叉树的某个位置，用right指向第二个二叉树的同一位置。 首先，当2个二叉树都不为空的时候，将第一个二叉树的根节点用一个TreeNode结构体的left表示，第二个二叉树的节点用right表示，然后将这个结构体压入stack当中。 如果stack不为空，取出stack的top元素，判断left和right指向的节点的val是否相同，
如果不相同则表明2个二叉树不相同；如果相同则表明2个二叉树当前位置的节点值是一样的，那么继续把当前位置的节点的左子节点和右子节点压入stack中，直到stack为空。如果到stack为空都没发现不相同的节点，那么这2个二叉树就是相同的。
代码：
#include <iostream> #include <stack> using namespace std; /** * 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<TreeNode> s; if (p == NULL || q == NULL) { return p == NULL && q == NULL; } TreeNode t(0); t.left = p; t.right = q; s.push(t); while(!s.empty()) { TreeNode current_state = s.top(); s.pop(); if(current_state.left->val != current_state.right->val) { return false; } if(current_state.left->left != NULL && current_state.right->left != NULL) { TreeNode left(0); left.left = current_state.left->left; left.right = current_state.right->left; s.push(left); } else if((current_state.left->left == NULL && current_state.right->left != NULL) || (current_state.left->left != NULL && current_state.right->left == NULL)) { return false; } if(current_state.left->right != NULL && current_state.right->right != NULL) { TreeNode right(0); right.left = current_state.left->right; right.right = current_state.right->right; s.push(right); } else if((current_state.left->right == NULL && current_state.right->right != NULL) || (current_state.left->right != NULL && current_state.right->right == NULL)) { return false; } } return true; } }; int main(int argc, const char * argv[]) { // insert code here... std::cout << "Hello, World!\n"; return 0; }