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
  }
};