|
1 | 1 | ##题目地址 |
2 | 2 | https://leetcode-cn.com/problems/same-tree/ |
3 | 3 |
|
4 | | -##思路 |
| 4 | +（没写完） |
5 | 5 |
|
6 | | -这道题目和101 基本是一样的 |
| 6 | +#100. 相同的树 |
| 7 | + |
| 8 | +给定两个二叉树，编写一个函数来检验它们是否相同。 |
| 9 | + |
| 10 | +如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 |
| 11 | + |
| 12 | +<imgsrc='../pics/100.相同的树.png'width=600> </img></div> |
| 13 | + |
| 14 | +#思路 |
| 15 | + |
| 16 | +在[二叉树：我对称么？](https://mp.weixin.qq.com/s/Kgf0gjvlDlNDfKIH2b1Oxg)中，我们讲到对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了**其实我们要比较的是两个树（这两个树是根节点的左右子树）**，所以在递归遍历的过程中，也是要同时遍历两棵树。 |
| 17 | + |
| 18 | +理解这一本质之后，就会发现，求二叉树是否对称，和求二叉树是否相同几乎是同一道题目。 |
| 19 | + |
| 20 | +**如果没有读过[二叉树：我对称么？](https://mp.weixin.qq.com/s/Kgf0gjvlDlNDfKIH2b1Oxg)这一篇，请认真读完再做这道题，就会有感觉了。** |
| 21 | + |
| 22 | +递归三部曲中： |
| 23 | + |
| 24 | +1. 确定递归函数的参数和返回值 |
| 25 | + |
| 26 | +我们要比较的是两个树是否是相互相同的，参数也就是两个树的根节点。 |
| 27 | + |
| 28 | +返回值自然是bool类型。 |
| 29 | + |
| 30 | +代码如下： |
| 31 | +``` |
| 32 | +bool compare(TreeNode* tree1, TreeNode* tree2) |
| 33 | +``` |
| 34 | + |
| 35 | +分析过程同[二叉树：我对称么？](https://mp.weixin.qq.com/s/Kgf0gjvlDlNDfKIH2b1Oxg)。 |
| 36 | + |
| 37 | +2. 确定终止条件 |
| 38 | + |
| 39 | +**要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。** |
| 40 | + |
| 41 | +节点为空的情况有： |
| 42 | + |
| 43 | +* tree1为空，tree2不为空，不对称，return false |
| 44 | +* tree1不为空，tree2为空，不对称 return false |
| 45 | +* tree1，tree2都为空，对称，返回true |
| 46 | + |
| 47 | +此时已经排除掉了节点为空的情况，那么剩下的就是tree1和tree2不为空的时候： |
| 48 | + |
| 49 | +* tree1、tree2都不为空，比较节点数值，不相同就return false |
| 50 | + |
| 51 | +此时tree1、tree2节点不为空，且数值也不相同的情况我们也处理了。 |
| 52 | + |
| 53 | +代码如下： |
| 54 | +``` |
| 55 | +if (tree1 == NULL && tree2 != NULL) return false; |
| 56 | +else if (tree1 != NULL && tree2 == NULL) return false; |
| 57 | +else if (tree1 == NULL && tree2 == NULL) return true; |
| 58 | +else if (tree1->val != tree2->val) return false; // 注意这里我没有使用else |
| 59 | +``` |
| 60 | + |
| 61 | +分析过程同[二叉树：我对称么？](https://mp.weixin.qq.com/s/Kgf0gjvlDlNDfKIH2b1Oxg) |
| 62 | + |
| 63 | +3. 确定单层递归的逻辑 |
| 64 | + |
| 65 | +* 比较二叉树是否相同 ：传入的是tree1的左孩子，tree2的右孩子。 |
| 66 | +* 如果左右都相同就返回true ，有一侧不相同就返回false 。 |
| 67 | + |
| 68 | +代码如下： |
| 69 | + |
| 70 | +``` |
| 71 | +bool outside = compare(tree1->left, tree2->right); // 左子树：左、 右子树：左 |
| 72 | +bool inside = compare(tree1->right, tree2->left); // 左子树：右、 右子树：右 |
| 73 | +bool isSame = outside && inside; // 左子树：中、 右子树：中（逻辑处理） |
| 74 | +return isSame; |
| 75 | +``` |
| 76 | +-------------------------------------------------------------- 写到这 |
| 77 | +最后递归的C++整体代码如下： |
| 78 | + |
| 79 | +``` |
| 80 | +class Solution { |
| 81 | +public: |
| 82 | + bool compare(TreeNode* left, TreeNode* right) { |
| 83 | + // 首先排除空节点的情况 |
| 84 | + if (left == NULL && right != NULL) return false; |
| 85 | + else if (left != NULL && right == NULL) return false; |
| 86 | + else if (left == NULL && right == NULL) return true; |
| 87 | + // 排除了空节点，再排除数值不相同的情况 |
| 88 | + else if (left->val != right->val) return false; |
| 89 | +
|
| 90 | + // 此时就是：左右节点都不为空，且数值相同的情况 |
| 91 | + // 此时才做递归，做下一层的判断 |
| 92 | + bool outside = compare(left->left, right->right); // 左子树：左、 右子树：右 |
| 93 | + bool inside = compare(left->right, right->left); // 左子树：右、 右子树：左 |
| 94 | + bool isSame = outside && inside; // 左子树：中、 右子树：中 （逻辑处理） |
| 95 | + return isSame; |
| 96 | +
|
| 97 | + } |
| 98 | + bool isSymmetric(TreeNode* root) { |
| 99 | + if (root == NULL) return true; |
| 100 | + return compare(root->left, root->right); |
| 101 | + } |
| 102 | +}; |
| 103 | +``` |
| 104 | + |
| 105 | +**我给出的代码并不简洁，但是把每一步判断的逻辑都清楚的描绘出来了。** |
| 106 | + |
| 107 | +如果上来就看网上各种简洁的代码，看起来真的很简单，但是很多逻辑都掩盖掉了，而题解可能也没有把掩盖掉的逻辑说清楚。 |
| 108 | + |
| 109 | +**盲目的照着抄，结果就是：发现这是一道“简单题”，稀里糊涂的就过了，但是真正的每一步判断逻辑未必想到清楚。** |
| 110 | + |
| 111 | +当然我可以把如上代码整理如下： |
| 112 | +这道题目本质上和[二叉树：我对称么？](https://mp.weixin.qq.com/s/Kgf0gjvlDlNDfKIH2b1Oxg)是一样，因为 |
7 | 113 |
|
8 | 114 | ##递归 |
9 | 115 |
|
@@ -42,7 +148,6 @@ public: |
42 | 148 | if (!leftNode && !rightNode) { // |
43 | 149 | continue; |
44 | 150 | } |
45 | | -
|
46 | 151 | // |
47 | 152 | if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) { |
48 | 153 | return false; |
|