怎么做网站劳务中介,html做旅游网站,菜单制作软件app,wordpress 邮件模板想要精通算法和SQL的成长之路 - 二叉树的判断问题 前言一. 相同的树二. 对称二叉树三. 判断子树 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 相同的树
原题链接
这题目典型的递归题#xff1a;
如果两个节点都是null#xff0c;我们返回true。如果两个节点一个nul… 想要精通算法和SQL的成长之路 - 二叉树的判断问题 前言一. 相同的树二. 对称二叉树三. 判断子树 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 相同的树
原题链接
这题目典型的递归题
如果两个节点都是null我们返回true。如果两个节点一个null一个非空返回false。最后满足条件当前两个节点值相等并且两个节点的左子树相等右子树也相等。
代码如下
public boolean isSameTree(TreeNode p, TreeNode q) {if (p null q null) {return true;}if (p null || q null) {return false;}return p.val q.val isSameTree(p.left, q.left) isSameTree(p.right, q.right);
}二. 对称二叉树
原题链接 这个题目我们依旧使用递归算法。我们可以在第一题的基础上做一个改变。 一致性代码
return p.val q.val isSameTree(p.left, q.left) isSameTree(p.right, q.right);对称代码
return p.val q.val isSameTree(p.left, q.right) isSameTree(p.right, q.left);最终完整代码如下
public boolean isSymmetric(TreeNode root) {return helper(root.left, root.right);
}public boolean helper(TreeNode p, TreeNode q) {if (p null q null) {return true;}if (p null || q null) {return false;}return p.val q.val helper(p.left, q.right) helper(p.right, q.left);
}三. 判断子树
原题链接 此题依旧是第一题的一个进阶版判断B是否是A的子树可以等同于
A 和 B 是否相同A.left 和 B 是否相同A.right 和 B 是否相同以此类推…
那么在第一题的基础上我们有了函数去判断两棵树是否相等我们只需要完成上面的判断即可
public boolean isSubtree(TreeNode root, TreeNode subRoot) {// 特判root肯定不能为nullif (root null) {return false;}// 特判subRoot子树允许为nullif (subRoot null) {return true;}return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot) || isSameTree(root, subRoot);
}public boolean isSameTree(TreeNode p, TreeNode q) {if (p null q null) {return true;}if (p null || q null) {return false;}if (p.val ! q.val) {return false;}return p.val q.val isSameTree(p.left, q.left) isSameTree(p.right, q.right);
}
