0100._Same_Tree

100. Same Tree

难度: Easy

刷题内容

原题连接

内容描述

给定两个二叉树,编写一个函数来检验它们是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例 1:

1
2
3
4
5
6
7
输入:       1         1
/ \ / \
2 3 2 3

[1,2,3], [1,2,3]

输出: true

示例 2:

1
2
3
4
5
6
7
输入:      1          1
/ \
2 2

[1,2], [1,null,2]

输出: false

示例 3:

1
2
3
4
5
6
7
输入:       1         1
/ \ / \
2 1 1 2

[1,2,1], [1,1,2]

输出: false

解题方案

思路 1
**- 时间复杂度: O(N)**- 空间复杂度: O(1)**

递归解法

  1. 获取当前二叉树的中序遍历结果数组
  2. 判断上步的数组是否是一个有序数组

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} p
* @param {TreeNode} q
* @return {boolean}
*/
var isSameTree = function(p, q) {
if (p) {
return p && !!q && (p.val === q.val) && isSameTree(p.left, q.left) && isSameTree(p.right,q.right)
} else {
return !q
}
};