Create 100.same-tree.md

daydaygo · daydaygo · commit 7dee275b1651 · 2020-11-16T10:44:08.000+08:00
diff --git a/problems/100.same-tree.md b/problems/100.same-tree.md
@@ -0,0 +1,230 @@
+## 题目地址（100. 相同的树）
+
+https://leetcode-cn.com/problems/same-tree/
+
+## 题目描述
+
+```
+给定两个二叉树，编写一个函数来检验它们是否相同。
+
+如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
+
+示例 1:
+
+输入:       1         1
+          / \       / \
+         2   3     2   3
+
+        [1,2,3],   [1,2,3]
+
+输出: true
+示例 2:
+
+输入:      1          1
+          /           \
+         2             2
+
+        [1,2],     [1,null,2]
+
+输出: false
+示例 3:
+
+输入:       1         1
+          / \       / \
+         2   1     1   2
+
+        [1,2,1],   [1,1,2]
+
+输出: false
+```
+
+## 前置知识
+
+- 递归
+- 层序遍历
+- 前中序确定一棵树
+
+## 递归
+
+### 思路
+
+最简单的想法是递归，这里先介绍下递归三要素
+
+- 递归出口，问题最简单的情况
+- 递归调用总是去尝试解决更小的问题，这样问题才会被收敛到最简单的情况
+- 递归调用的父问题和子问题没有交集
+
+尝试用递归去解决相同的树
+
+1.  分解为子问题，相同的树分解为左子是否相同，右子是否相同
+2.  递归出口: 当树高度为 1 时，判断递归出口
+
+### 代码
+
+语言支持：JS, Go, PHP
+
+JS Code：
+
+```js
+var isSameTree = function (p, q) {
+  if (!p || !q) {
+    return !p && !q;
+  }
+  return (
+    p.val === q.val &&
+    isSameTree(p.left, q.left) &&
+    isSameTree(p.right, q.right)
+  );
+};
+```
+
+Go Code:
+
+```go
+func isSameTree(p *TreeNode, q *TreeNode) bool {
+	if p == nil || q == nil {
+		return p==nil&&q==nil
+	}
+	return p.Val == q.Val && isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
+}
+```
+
+PHP Code:
+
+```php
+class Solution
+{
+
+    /**
+     * @param TreeNode $p
+     * @param TreeNode $q
+     * @return Boolean
+     */
+    function isSameTree($p, $q)
+    {
+        if (!$p || !$q) {
+            return !$p && !$q;
+        }
+        return $p->val == $q->val &&
+            $this->isSameTree($p->left, $q->left) &&
+            $this->isSameTree($p->right, $q->right);
+    }
+}
+```
+
+**复杂度分析**
+
+- 时间复杂度：$O(N)$，其中 N 为树的节点数。
+- 空间复杂度：$O(h)$，其中 h 为树的高度。
+
+## 层序遍历
+
+### 思路
+
+判断两棵树是否相同，只需要判断树的整个结构相同, 判断树的结构是否相同，只需要判断树的每层内容是否相同。
+
+### 代码
+
+语言支持：JS
+
+JS Code：
+
+```js
+var isSameTree = function (p, q) {
+  let curLevelA = [p];
+  let curLevelB = [q];
+
+  while (curLevelA.length && curLevelB.length) {
+    let nextLevelA = [];
+    let nextLevelB = [];
+    const isOK = isSameCurLevel(curLevelA, curLevelB, nextLevelA, nextLevelB);
+    if (isOK) {
+      curLevelA = nextLevelA;
+      curLevelB = nextLevelB;
+    } else {
+      return false;
+    }
+  }
+
+  return true;
+};
+
+function isSameCurLevel(curLevelA, curLevelB, nextLevelA, nextLevelB) {
+  if (curLevelA.length !== curLevelB.length) {
+    return false;
+  }
+  for (let i = 0; i < curLevelA.length; i++) {
+    if (!isSameNode(curLevelA[i], curLevelB[i])) {
+      return false;
+    }
+    curLevelA[i] && nextLevelA.push(curLevelA[i].left, curLevelA[i].right);
+    curLevelB[i] && nextLevelB.push(curLevelB[i].left, curLevelB[i].right);
+  }
+  return true;
+}
+
+function isSameNode(nodeA, nodeB) {
+  if (!nodeA || !nodeB) {
+    return nodeA === nodeB;
+  }
+  return nodeA.val === nodeB.val;
+  // return nodeA === nodeB || (nodeA && nodeB && nodeA.val === nodeB.val);
+}
+```
+
+**复杂度分析**
+
+- 时间复杂度：$O(N)$，其中 N 为树的节点数。
+- 空间复杂度：$O(Q)$，其中 Q 为队列的长度最大值，在这里不会超过相邻两层的节点数的最大值。
+
+## 前中序确定一棵树
+
+### 思路
+
+前序和中序的遍历结果确定一棵树，那么当两棵树前序遍历和中序遍历结果都相同，那是否说明两棵树也相同。
+
+### 代码
+
+语言支持：JS
+
+JS Code：
+
+```js
+var isSameTree = function (p, q) {
+  const preorderP = preorder(p, []);
+  const preorderQ = preorder(q, []);
+  const inorderP = inorder(p, []);
+  const inorderQ = inorder(q, []);
+  return (
+    preorderP.join("") === preorderQ.join("") &&
+    inorderP.join("") === inorderQ.join("")
+  );
+};
+
+function preorder(root, arr) {
+  if (root === null) {
+    arr.push(" ");
+    return arr;
+  }
+  arr.push(root.val);
+  preorder(root.left, arr);
+  preorder(root.right, arr);
+  return arr;
+}
+
+function inorder(root, arr) {
+  if (root === null) {
+    arr.push(" ");
+    return arr;
+  }
+  inorder(root.left, arr);
+  arr.push(root.val);
+  inorder(root.right, arr);
+  return arr;
+}
+```
+
+**复杂度分析**
+
+- 时间复杂度：$O(N)$，其中 N 为树的节点数。
+- 空间复杂度：使用了中序遍历的结果数组，因此空间复杂度为 $O(N)$，其中 N 为树的节点数。
