package main

import (
	"fmt"
)

// TreeNode ...
// type TreeNode struct {
// 	Val   int
// 	Left  *TreeNode
// 	Right *TreeNode
// }

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
	// leaf node, eq
	// one of p/q is not nil, ne
	if p == nil || q == nil {
		return p == q
	}
	if p.Val != q.Val {
		return false
	}
	// preoder traversal, DLR
	return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

func test100() {
	/**
	 * t1:  5
	 *     / \
	 *    1   4
	 *       / \
	 *      2   3
	 */
	t1l := TreeNode{1, nil, nil}
	t1rl := TreeNode{2, nil, nil}
	t1rr := TreeNode{3, nil, nil}
	t1r := TreeNode{4, &t1rl, &t1rr}
	t1 := &TreeNode{5, &t1l, &t1r}
	/**
	 * t2: same as t1
	 */
	t2l := TreeNode{1, nil, nil}
	t2rl := TreeNode{2, nil, nil}
	t2rr := TreeNode{3, nil, nil}
	t2r := TreeNode{4, &t2rl, &t2rr}
	t2 := &TreeNode{5, &t2l, &t2r}
	fmt.Println(isSameTree(t1, t2))
}