【剑指offer】树的子结构

树的子结构

http://www.nowcoder.com/questionTerminal/6e196c44c7004d15b1610b9afca8bd88

思路:
第一步:在树A中找到和树B的节点一样的节点R
第二部:判断树A以R为根节点的子树是不是包含树B一样的结构

摘自书上,思路很清晰了,做一个说明:
第一步其实是对树A进行遍历,遍历的话,你可以选深度遍历,也可以选层次遍历,都ok
// 刚开始写的层次遍历,感觉代码稍微有点长,就换成了深度遍历

public class Solution {

    public boolean jude(TreeNode node, TreeNode no) { // 第二步
        if (no == null) {
            return true;
        }
        if (node == null) {
            return false;
        }

        if (node.val == no.val) {
            return jude(node.left, no.left) && jude(node.right, no.right);
        } else {
            return false;
        }
    }

    public boolean HasSubtree(TreeNode root1, TreeNode root2) { // 第一步 深度遍历
        if (root1 == null || root2 == null) {
            return false;
        }
        return jude(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    }
}
全部评论

相关推荐

鬼迹人途:你去投一投尚游游戏,服务器一面,第一个图算法,做完了给你一个策略题,你给出方案他就提出低概率问题,答不上当场给你挂
点赞 评论 收藏
分享
Z_eus:别打招呼直接发你的优势
点赞 评论 收藏
分享
评论
8
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务