个人网站需要什么页面,和县网站定制,咖啡公司网站建设策划书,粉红色网站asp我希望通过这道题#xff0c;能进一步了解递归思想和“树是递归定义的”这句话 分析
我们的目的是写一个方法来检验两棵树是否相同
什么叫“两棵树相同”#xff1f;——相同的位置存在相同的结点
有三种情况#xff1a;1、两棵树一颗为空一颗不为空——不相同#xff… 我希望通过这道题能进一步了解递归思想和“树是递归定义的”这句话 分析
我们的目的是写一个方法来检验两棵树是否相同
什么叫“两棵树相同”——相同的位置存在相同的结点
有三种情况1、两棵树一颗为空一颗不为空——不相同2、两棵树都是空——相同3、两个都不是空——不一定
代码
public class SameBinaryTree {public class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(){}TreeNode(int val){this.val val;}}public boolean isSameTree(TreeNode p, TreeNode q) {//两棵树都是空——相同if(p null q null){return true;}//两棵树一颗为空一颗不为空——不相同if((p null)(q ! null) || (p ! null) (q null)){return false;}//两个都不是空——不一定所以我们要对其节点值进行判断if(p.val ! q.val){return false;}//如果这两个根节点相同的话然后去检查其左子树和右子树是否分别相等return isSameTree(p.left,q.left) isSameTree(p.right,q.right);}
}它是怎样使用递归的
因为树是递归定义的所以对于二叉树相关的题我们常使用递归思想。
使用递归的两个条件
1、终止条件 a、两棵树一颗为空一颗不为空——不相同b、两棵树都是空——相同
2、调用自身 两棵树是否相同不过就是——“根节点的值是否相同/根节点的左子树是否相同/根节点的右节点是否相同” 我们的方法表示的含义就是“根节点为 参数1 和参数2 的两棵树是否相同”。那么 参数为参数1.left 参数2.left意思就是——“两个根节点的左子树是否相同”
