0%

leetcode每日一题-相同的树

Posted on In ,

相同的树

image1

方法一：递归

  1. 如果节点$p$和节点$q$都为空，那么两个节点相同，返回$true$。
  2. 如果一方为空，另一方不为空，那么就不相同，返回$false$。
  3. 如果两个节点都不为空，但是值不同，那么就不相同，返回$false$。
  4. 如果两个节点都不为空且值相同，那么就递归地比较节点的左右子树是否相同。
1
/**
2
 * Definition for a binary tree node.
3
 * public class TreeNode {
4
 *     int val;
5
 *     TreeNode left;
6
 *     TreeNode right;
7
 *     TreeNode() {}
8
 *     TreeNode(int val) { this.val = val; }
9
 *     TreeNode(int val, TreeNode left, TreeNode right) {
10
 *         this.val = val;
11
 *         this.left = left;
12
 *         this.right = right;
13
 *     }
14
 * }
15
 */
16
class Solution {
17
    public boolean isSameTree(TreeNode p, TreeNode q) {
18
        if(p == null && q == null){
19
            return true;
20
        }
21
        if(p == null || q == null){
22
            return false;
23
        }
24
        return p.val==q.val && isSameTree(p.left,q.left) && isSameTree(p.right, q.right);
25
    }
26
}

复杂度分析：

  • 时间复杂度：$O(min(m,n))$，$m$和$n$分别是两个二叉树的节点数。
  • 空间复杂度：$O(min(m,n))$。

方法二：广度优先搜索

也可以通过广度优先搜索判断两个二叉树是否相同。同样首先判断两个二叉树是否为空，如果两个二叉树都不为空，则从两个二叉树的根节点开始广度优先搜索。

使用两个队列分别存储两个二叉树的节点。初始时将两个二叉树的根节点分别加入两个队列。每次从两个队列各取出一个节点，进行如下比较操作。

  1. 比较两个节点的值，如果两个节点的值不相同则两个二叉树一定不同；

  2. 如果两个节点的值相同，则判断两个节点的子节点是否为空，如果只有一个节点的左子节点为空，或者只有一个节点的右子节点为空，则两个二叉树的结构不同，因此两个二叉树一定不同；

  3. 如果两个节点的子节点的结构相同，则将两个节点的非空子节点分别加入两个队列，子节点加入队列时需要注意顺序，如果左右子节点都不为空，则先加入左子节点，后加入右子节点。

如果搜索结束时两个队列同时为空，则两个二叉树相同。如果只有一个队列为空，则两个二叉树的结构不同，因此两个二叉树不同。

1
class Solution {
2
    public boolean isSameTree(TreeNode p, TreeNode q) {
3
        if (p == null && q == null) {
4
            return true;
5
        } else if (p == null || q == null) {
6
            return false;
7
        }
8
        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
9
        Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
10
        queue1.offer(p);
11
        queue2.offer(q);
12
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
13
            TreeNode node1 = queue1.poll();
14
            TreeNode node2 = queue2.poll();
15
            if (node1.val != node2.val) {
16
                return false;
17
            }
18
            TreeNode left1 = node1.left, right1 = node1.right, left2 = node2.left, right2 = node2.right;
19
            if (left1 == null ^ left2 == null) {
20
                return false;
21
            }
22
            if (right1 == null ^ right2 == null) {
23
                return false;
24
            }
25
            if (left1 != null) {
26
                queue1.offer(left1);
27
            }
28
            if (right1 != null) {
29
                queue1.offer(right1);
30
            }
31
            if (left2 != null) {
32
                queue2.offer(left2);
33
            }
34
            if (right2 != null) {
35
                queue2.offer(right2);
36
            }
37
        }
38
        return queue1.isEmpty() && queue2.isEmpty();
39
    }
40
}

复杂度分析：

  • 时间复杂度：$O(min(m,n))$。
  • 空间复杂度：$O(min(m,n))$。