572_subtree_of_another_tree

572. 另一个树的子树 简单

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

示例 1:
给定的树 s:

     3
    / \
   4   5
  / \
 1   2

给定的树 t：

   4 
  / \
 1   2

返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。

示例 2:
给定的树 s：

     3
    / \
   4   5
  / \
 1   2
    /
   0

给定的树 t：

   4
  / \
 1   2

返回 false。

代码参考：

package main

import "fmt"

func main() {
    s := &TreeNode{Val: 3}
    s.Left = &TreeNode{Val: 4}
    s.Left.Left = &TreeNode{Val: 1}
    s.Left.Right = &TreeNode{Val: 2}
    // s.Left.Right.Left = &TreeNode{Val: 0} // false
    s.Right = &TreeNode{Val: 5}

    t := &TreeNode{Val: 4}
    t.Left = &TreeNode{Val: 1}
    t.Right = &TreeNode{Val: 2}

    fmt.Println(isSubtree(s, t)) // true
}

func isSubtree(s *TreeNode, t *TreeNode) bool {
    if isSame(s, t) {
        return true // bingo
    }

    if s == nil {
        return false // 向下不会再相等
    }

    return isSubtree(s.Left, t) || isSubtree(s.Right, t)
}

func isSame(t1, t2 *TreeNode) bool {
    if t1 == nil && t2 == nil {
        return true
    }
    if t1 == nil || t2 == nil {
        return false
    }

    return t1.Val == t2.Val && isSame(t1.Left, t2.Left) && isSame(t1.Right, t2.Right)
}