题目来源:剑指 Offer 26. 树的子结构
输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构, 即 A中有出现和B相同的结构和节点值。
解题思路:如果树A或树B为空则不满足,直接返回。否则判断B是否为A节点的子结构,或A的左(右)子树的子结构。在递归函数中进行判断:如果B节点为空,表明已经匹配完成,返回true;如果B不为空,而A为空,或A、B节点的值不相同,则匹配失败,返回false;如果A、B的值相同则继续比较A、B的左右子树。
时间复杂度:O(N)
空间复杂度:O(1)
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
return (A != null && B != null) && (recur(A, B) ||
isSubStructure(A.left, B) || isSubStructure(A.right, B));
}
boolean recur(TreeNode A, TreeNode B) {
if (B == null) return true;
if (A == null || A.val != B.val) return false;
return recur(A.left, B.left) && recur(A.right, B.right);
}
}
题目来源:剑指 Offer 27. 二叉树的镜像
请完成一个函数,输入一个二叉树,该函数输出它的镜像。
解题思路:对树的根节点调用递归函数。递归函数中执行:若节点为空直接返回;否则交换该节点的左右子树,并分别对其调用递归函数,最后返回节点本身。
时间复杂度:O(N)
空间复杂度:O(1)
class Solution {
public TreeNode mirrorTree(TreeNode root) {
return recur(root);
}
TreeNode recur(TreeNode root) {
if (root == null) return null;
TreeNode tmpNode = root.left;
root.left = recur(root.right);
root.right = recur(tmpNode);
return root;
}
}
题目来源:剑指 Offer 28. 对称的二叉树
请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。
解题思路:如果根节点为空则满足,直接返回,否则将其左右子树传入递归函数。
递归函数执行过程如下:如果传入的两个节点都为空,则判断结束,条件满足;若有一个不为空或者两个节点的值不相同,则判断结束,条件不满足;如果两个节点的值相同,则继续递归调用,分别比较左左与右右、左右与右左是否满足。
时间复杂度:O(N)
空间复杂度:O(1)
class Solution {
public boolean isSymmetric(TreeNode root) {
return (root == null) || (recur(root.left, root.right));
}
boolean recur(TreeNode left, TreeNode right) {
if (left == null && right == null) return true;
if (left == null || right == null || left.val != right.val) return false;
return recur(left.left, right.right) && recur(left.right, right.left);
}
}