LeetCode100——相同的树
我的LeetCode代码仓:https://github.com/617076674/LeetCode
原题链接:https://leetcode-cn.com/problems/same-tree/description/
题目描述:
知识点:递归
思路:利用二叉树的递归性质判断两棵二叉树是否相同
本题是简单的递归的应用。
递归终止条件:
(1)如果p和q均为null,直接返回true。
(2)如果p和q只有其中之一为null,直接返回false。
(3)如果p和q两者均不为null且p的值和q的值不相等,直接返回false。
递归过程:
如果p和q两者均不为null且p的值和q的值不相等,则递归判断p的左子树是否和q的左子树相等,p的右子树是否和q的右子树相等,只有两者都相等时,才返回true。
时间复杂度是O(n),其中n为二叉树的节点个数。空间复杂度即递归深度,是O(h),其中h为二叉树的高度。
JAVA代码:
public class Solution {
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 != 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);
}
}
}
}
LeetCode解题报告: