package main

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

func isSymmetricIter(lNode *TreeNode, rNode *TreeNode) bool {
	if lNode == nil || rNode == nil {
		return lNode == rNode
	}
	if lNode.Val != rNode.Val {
		return false
	}
	return isSymmetricIter(lNode.Left, rNode.Right) && isSymmetricIter(lNode.Right, rNode.Left)
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	}
	return isSymmetricIter(root.Left, root.Right)
}

// func main() {
// 	/**
// 	 * 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:   1
// 	 *     /   \
// 	 *    2     2
// 	 *   / \   / \
// 	 *  4   3 3   4
// 	 */
// 	t2ll := TreeNode{4, nil, nil}
// 	t2lr := TreeNode{3, nil, nil}
// 	t2l := TreeNode{2, &t2ll, &t2lr}
// 	t2rl := TreeNode{3, nil, nil}
// 	t2rr := TreeNode{4, nil, nil}
// 	t2r := TreeNode{2, &t2rl, &t2rr}
// 	t2 := &TreeNode{1, &t2l, &t2r}
// 	fmt.Println(isSymmetric(t1))
// 	fmt.Println(isSymmetric(t2))
// }