题目描述
给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例
输入:
1 1
/ \ / \
2 3 2 3
输出:
true
写在前面
100啦~[耶] o(*≧▽≦)ツ
本文答案参考自 LeetCode 官方题解 和 https://www.cnblogs.com/xiaolovewei/p/7763867 。
这题难度是简单。
解法1:深度优先搜索
对这两棵树同时进行深度优先搜索,如果有一次搜索时两节点的数值不一样,则返回 false。
解法2:广度优先搜索
同理,对这两棵树同时进行广度优先搜索,如果有一次搜索时两节点的数值不一样,则返回 false。
补充:深度优先搜索和广度优先搜索的伪代码
深度优先搜索:
//递归
if (node!=null)
{
visit(node);
dfs(node -> left);
dfs(node -> right);
}
//迭代
Stack<TreeNode> stack=new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node=stack.pop();
if(node.left != null)
stack.push(node.right);
if(node.right != null)
stack.push(node.left);
visit(node.val);
}
广度优先搜索:
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(node.left != null)
queue.offer(node.left);
if(node.right != null)
queue.offer(node.right);
visit(node);
}