obzva.go

/*
풀이
- 재귀함수를 이용해서 풀이할 수 있습니다
Big O
- N: 트리 노드의 개수
- H: 트리의 높이 (logN <= H <= N)
- Time complexity: O(N)
  - 모든 노드를 최대 1번 탐색합니다
- Space complexity: O(H)
  - 재귀 호출 스택의 깊이는 H에 비례하여 증가합니다
*/

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 func isSameTree(p *TreeNode, q *TreeNode) bool {
	// base case
	if p == nil && q == nil {
		return true
	} else if p == nil || q == nil {
		return false
	}

	if p.Val != q.Val {
		return false
	}

	if !isSameTree(p.Left, q.Left) || !isSameTree(p.Right, q.Right) {
		return false
	}

	return true
}