LeetCode集锦（二十一） - 第100题 Same Tree

发表于 | 分类于 |

问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
Given two binary trees, write a function to check if they are the same or not. 

 Two binary trees are considered the same if they are structurally identical and the nodes have the same value. 

 Example 1: 


Input:     1         1
          / \       / \
         2   3     2   3

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

Output: true


 Example 2: 


Input:     1         1
          /           \
         2             2

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

Output: false


 Example 3: 


Input:     1         1
          / \       / \
         2   1     1   2

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

Output: false

翻译:

给定两棵二叉树，编写一个函数来检查它们是否相同。
如果两个二叉树在结构上是相同的，并且节点具有相同的值，则认为它们是相同的。
示例1:

1
2
3
4
5
6
>            1         1
>           / \       / \
>          2   3     2   3
>         [1,2,3],   [1,2,3]
>
>

输出:true
示例2:

1
2
3
4
5
>          1         1
>         /           \
>        2             2
>       [1,2],[1,null, 2)
>

输出:false
示例3:

1
2
3
4
5
>           1         1
>          / \       / \
>         2   1     1   2
>        [1,2,1],   [1,1,2]
>

输出:false

解题思路

本题判断两个树是否相等，我们第一时间想到的就是遍历树节点，看看树节点是否一致（内容）。遍历树的方法有前序遍历，中序遍历，和后序遍历，这边选择了后序遍历。

解题方法

  1. 后序遍历方式，代码如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }

        boolean left = isSameTree(p.left, q.left);
        boolean right = isSameTree(p.right, q.right);

        return left && right && p.val == q.val;
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    时间复杂度: 该方案用了递归遍历树，不要判断时间复杂度，而且树的遍历复杂度都说不好，且记为O(n)

    空间复杂度: 该方案使用了没有使用额外空间，所以空间复杂度是O(n)=O(1);

总结

本题的大致解法如上所诉按照正常遍历树的方式来就好，选择自己喜欢的遍历方式，但是就是不会算树的时间复杂度。。。