想要精通算法和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);
}
1
2
3
4
5
6
7
8
9

二. 对称二叉树

原题链接

这个题目，我们依旧使用递归算法。我们可以在第一题的基础上，做一个改变。
一致性代码：

return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
1

对称代码：

return p.val == q.val && isSameTree(p.left, q.right) && isSameTree(p.right, q.left);
1

最终完整代码如下：

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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

三. 判断子树

原题链接

此题依旧是第一题的一个进阶版，判断B是否是A的子树可以等同于：

• A 和 B 是否相同？
• A.left 和 B 是否相同？
• A.right 和 B 是否相同？
• 以此类推…

那么在第一题的基础上，我们有了函数去判断两棵树是否相等，我们只需要完成上面的判断即可：

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
	// 特判：root肯定不能为null
    if (root == null) {
        return false;
    }
    // 特判：subRoot子树允许为null
    if (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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24