[LeetCode] 572. Subtree of Another Tree (golang)

문제

---

Subtree of Another Tree - LeetCode

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise. A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants.

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

• 부분 트리 유무 확인

구현

---

• root트리 탐색 ( N )

• subRoot트리와 전체 일치 여부 확인 ( M )

시간 복잡도

• O(NM)

• 코드

  /**
   * Definition for a binary tree node.
   * type TreeNode struct {
   *     Val int
   *     Left *TreeNode
   *     Right *TreeNode}
   */
  func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
      result := searchRoot(root, subRoot)
      return result
  
  }
  
  func searchRoot(subTree *TreeNode, subRoot *TreeNode) bool {
      if (isEqualTree(subTree, subRoot)) {return true}
      if (subTree.Left != nil) {
          if (searchRoot(subTree.Left, subRoot)) {return true}
      }
      if (subTree.Right != nil) {
          if (searchRoot(subTree.Right, subRoot)) {return true}
      }
      return false
  }
  
  func isEqualTree(t1 *TreeNode, t2 *TreeNode) bool {
      if(t1 == nil && t2 == nil) {return true}
      if(t1 == nil || t2 == nil) {return false}
      if(t1.Val != t2.Val) {return false}
      if(!isEqualTree(t1.Left,t2.Left)) {return false}    
      if(!isEqualTree(t1.Right,t2.Right)) {return false}    
      
      return true
  }