首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >15 道二叉树手写算法题(三)

15 道二叉树手写算法题(三)

作者头像
乔戈里
发布2019-04-24 16:19:49
5130
发布2019-04-24 16:19:49
举报
文章被收录于专栏:Java那些事Java那些事

6. 子树

Leetcode 572. Subtree of Another Tree (Easy)

给定两棵树 s 和 t,题目要求判断 t 是不是 s 的子树,也就是 s 中存不存在一颗和 t 完全相同的树。下图中,s 中以 1 为根节点的子树和 t 完全相同,因此返回 true。

但如果只是 s 中的一部分和 t 相同是不满足题目要求的,例如下图中虽然 s 中以节点 1 为根节点的子树有 3 个节点的值和结构都和 t 相同,但是多了一个 5 节点,那么该子树和 t 就不完全相同,t 不是 s 的子树。

要判断两棵树是否完全相同很容易,只要同时遍历两棵树并判断每个节点是否相同即可。本题的求解可以转换成:判断以 s 为根节点的树是否和 t 相同,或者判断 s 的两个子树是否存在解。在两个子树上的求解可以继续使用该求解函数,因此很容易使用递归来实现。

public boolean isSubtree(TreeNode s, TreeNode t) {
    if (s == null)
        return false;
    return isSubtreeWithRoot(s, t) 
        || isSubtree(s.left, t) 
        || isSubtree(s.right, t);
}

private boolean isSubtreeWithRoot(TreeNode s, TreeNode t) {
    if (t == null && s == null)
        return true;
    if (t == null || s == null)
        return false;
    if (t.val != s.val)
        return false;
    return isSubtreeWithRoot(s.left, t.left) 
        && isSubtreeWithRoot(s.right, t.right);
}

7. 树的对称

Leetcode 101. Symmetric Tree (Easy)

题目要求判断一棵树是否对称。对称是指以该节点为对称中心,左右两边的值都相等。不要求一个节点的左右子树都要对称,所以不是先判断左右子树的值是否相同,再调用该求解函数判断左右子树是否也对称。

从定义可以看出,要判断的是以根节点为对称中心的两个节点是否相同,在遍历树的过程中,就要同时遍历这两个节点,遍历过程可以使用递归来实现。如果当前判断的两个节点是 t1 和 t2,在进入新的遍历递归函数时,下一层要遍历的应该是 (t1.left, t2.right) 和 (t1.right, t2.left)。

public boolean isSymmetric(TreeNode root) {
    if (root == null)
        return true; 
    return isSymmetric(root.left, root.right);
}

private boolean isSymmetric(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null)
        return true;
    if (t1 == null || t2 == null)
        return false;
    if (t1.val != t2.val)
        return false;
    return isSymmetric(t1.left, t2.right)
        && isSymmetric(t1.right, t2.left);
}
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-04-15,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员乔戈里 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 6. 子树
  • 7. 树的对称
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档