代码随想录——相同的树

题目

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

思路

递归三部曲：

1. 确定递归函数的参数和返回值
   比较两个树是否是相互相同的，参数就是两个数的根节点，返回值为boolean类型

2. 确定终止条件
   首先先单独处理两个节点有空节点的情况，避免后面比较数值的时候操作空指针
   节点有空的情况为：
   （1）tree1为空，tree2不为空，不对称，return false
   （2）tree1不为空，tree2为空，不对称 return false
   （3）tree1，tree2都为空，对称，返回true
   排除了节点有空的情况，剩下的就是两个节点都不为空的情况：tree1、tree2都不为空，比较节点数值，不相同就return false

3. 确定单层递归的逻辑
   比较二叉树是否相同，如果左右相同就返回true，有一侧不相同就返回false

java代码如下：

//递归法
class Soultion {
	public boolean isSameTree(TreeNode p,TreeNode q){
		if(p == null && q == null) return true;
		else if(q == null || p == null) return false;
		else if(q.val != p.val) return false;
		return isSameTree(q.left,p.left) && isSameTree(q.right,p.right);
	}
}

//迭代法
class Solution{
	public boolean isSameTree(TreeNode p,TreeNode q){
		if(p == null || q == null) return false;
		if(p == null && q == null) return false;
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(p);//代表左子树
		queue.offer(q);//代表右子树
		while(!queue.isEmpty()){
			TreeNode leftNode = queue.poll();//取左子树
			TreeNode rightNode = queue.poll();//取右子树
			if(leftNode == null && rightNode == null) continue;
			if(leftNode == null || rightNode == null || leftNode.val != rightNode.val) return false;
			queue.offer(leftNode.left);
			queue.offer(rightNode.left);
			queue.offer(leftNode.right);
			queue.offer(rightNode.right);
		}
		return true;
	}
}
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