100. 相同的树(深搜)

　　主要是要把握同方向搜索比较，其他比较简单，另外就是剪枝提高效率要牢记心中。

 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 flag = true; //判断是否相同的标记
13     bool isSameTree(TreeNode* p, TreeNode* q) {
14         if (!p && !q) return 1; //测试数据都为空则返回true
15         else if (!p || !q) return 0; //测试数据一个为空另一个不为空则返回false
16         dfs(p, q);    //递归判断
17         return flag; //返回结果
18     }
19     void dfs(TreeNode* L, TreeNode* R) {
20         if (!flag || !L && !R) return; //剪枝:如果已经判断为不相同,直接返回,或者到达叶子结点返回
21         else if (!L || !R || L->val != R->val) { //一节点空一个节点有值或者两个节点都有值但是值不相同,则两棵树不相同
22             flag = false;
23             return;
24         }
25         dfs(L->left, R->left); //同方向搜索比较
26         dfs(L->right, R->right);
27     }
28 };