企业网站建设与推广多少钱,备案的网站程序上传,wordpress使用环境,南山商城网站建设给你两棵二叉树的根节点 p 和 q #xff0c;编写一个函数来检验这两棵树是否相同 如果两个树在结构上相同#xff0c;并且节点具有相同的值#xff0c;则认为它们是相同的 输入#xff1a;p [1,2,3], q [1,2,3] 输出#xff1a;true 输入#xff1a;p [1,2], q [1,… 给你两棵二叉树的根节点 p 和 q 编写一个函数来检验这两棵树是否相同 如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的 输入p [1,2,3], q [1,2,3] 输出true 输入p [1,2], q [1,null,2] 输出false 输入p [1,2,1], q [1,1,2] 输出false 前言 两个二叉树相同当且仅当两个二叉树的结构完全相同且所有对应节点的值相同。因此可以通过搜索的方式判断两个二叉树是否相同。
方法深度优先搜索
如果两个二叉树都为空则两个二叉树相同。如果两个二叉树中有且只有一个为空则两个二叉树一定不相同。 如果两个二叉树都不为空那么首先判断它们的根节点的值是否相同若不相同则两个二叉树一定不同若相同再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程因此可以使用深度优先搜索递归地判断两个二叉树是否相同
bool isSameTree(struct TreeNode* p, struct 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);}
}
