另一个树的子树

题目描述

https://leetcode-cn.com/problems/subtree-of-another-tree/

解

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSubtree(s *TreeNode, t *TreeNode) bool {
    // 错误处理
    if s == nil || t == nil {
        return false
    }
    return isSubtreeDFS(s, t)
}

func isSubtreeDFS(root *TreeNode, t *TreeNode) bool {
    if root == nil {
        return false
    }
    if Check(root, t) {
        return true
    }
    if isSubtreeDFS(root.Left, t) {
        return true
    }
    return isSubtreeDFS(root.Right, t)
}

// 遍历每个节点 判断是否相等 相等开启判断模式
func Check(s *TreeNode, t *TreeNode) bool {
    if s == t && t == nil {
        return true
    }
    if s == nil || t == nil {
        return false
    }
    if s.Val != t.Val {
        return false
    }
    if !Check(s.Left, t.Left) {
        return false
    }
    return Check(s.Right, t.Right)
}

思路

选择中序遍历！这是简单模式的