100. 相同的树

Posted on Edited on In , ,
转载自Leet Code

题目描述

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 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

提示： - 两棵树上的节点数目都在范围 [0, 100] 内 - -104 <= Node.val <= 104

我的代码

\(T(M,N) = O(min(M,N))\), \(S(M,N) = O(min(M,N))\)

{.line-numbers}
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
39
40
41
42
43
44
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class MySolution100 // 前序遍历
{
    public boolean isSameTree(TreeNode p, TreeNode q) 
    {
    	Stack<TreeNode> stackP = new Stack(); TreeNode pointerP = p;
    	Stack<TreeNode> stackQ = new Stack(); TreeNode pointerQ = q;
    	
    	while (true)
    	{
    		if (pointerP!=null&&pointerQ!=null)
    		{
    			if (pointerP.val!=pointerQ.val) return false;
    			stackP.push(pointerP); stackQ.push(pointerQ);
    			pointerP = pointerP.left; pointerQ = pointerQ.left;
    		}
    		else if ((pointerP==null&&pointerQ!=null)||(pointerP!=null&&pointerQ==null))
    		{
    			return false;
    		}
    		else if (!stackP.isEmpty()&&!stackQ.isEmpty())
    		{
    			pointerP = stackP.pop().right;
    			pointerQ = stackQ.pop().right;
    		}
    		else if (stackP.size()!=stackQ.size()) return false;
    		else return true;
    	}
    }
}

方法一：DFS

\(T(M,N) = O(min(M,N))\), \(S(M,N) = O(min(M,N))\)

如果两个二叉树都为空，则两个二叉树相同； 如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同； 若两个二叉树都不为空， 则首先判断根节点的值是否相同，若不相同则两个二叉树一定不同； 若根节点的值相同，则再分别判断两个二叉树的左子树是否相同以及右子树是否相同。

这是一个递归的过程，因此可以使用DFS递归地判断。

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
class Solution100 
{
    public boolean isSameTree(TreeNode p, TreeNode q) 
    {
    	if (p==null&&q==null) return true;
    	else if (p==null||q==null) return false;
    	
    	else if (p.val!=q.val) return false;
    	else return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

方法二：BFS

\(T(M,N) = O(min(M,N))\), \(S(M,N) = O(min(M,N))\)

如果两个二叉树都为空，则两个二叉树相同； 如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同； 若两个二叉树都不为空， 则使用两个队列分别存储两个二叉树的节点，初始化为两棵树的根节点， 并每次分别从两个队列取出两个节点进行比较： 1. 比较两个节点的值，如果值不同则二叉树不同； 2. 若两个节点的值相同，则判断两个节点的子节点是否为空，如果只有一个节点的左/右节点为空，则二叉树不同； 3. 如果两个节点的子节点相同，则将两个节点的非空子节点分别加入两个队列（注意加入时的顺序，若左右子节点都不为空，则先加入左子节点，再加入右子节点）。

若搜索结束时两个队列为空则二叉树相同，否则说明两个二叉树的结构不同。

{.line-numbers}
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
class Solution100
{
    public boolean isSameTree(TreeNode p, TreeNode q) 
    {
    	if (p==null&&q==null) return true;
    	else if (p==null||q==null) return false;
    	
    	Queue<TreeNode> queue1 = new LinkedList();
    	Queue<TreeNode> queue2 = new LinkedList();
    	queue1.add(p); queue2.add(q);
    	
    	while (!queue1.isEmpty()&&!queue2.isEmpty())
    	{
    		TreeNode node1 = queue1.poll(); TreeNode node2 = queue2.poll();
    		if (node1.val!=node2.val) return false;
    		
    		TreeNode left1 = node1.left, right1 = node1.right, 
    				left2 = node2.left, right2 = node2.right;
            if (left1 == null ^ left2 == null) 
                return false;
            if (right1 == null ^ right2 == null)
                return false;
            if (left1 != null) 
                queue1.add(left1);
            if (right1 != null) 
                queue1.add(right1);
            if (left2 != null) 
                queue2.add(left2);
            if (right2 != null) 
                queue2.add(right2);
    	}
    	return queue1.isEmpty()&&queue2.isEmpty();
    }
}