101.E 对称二叉树

Problem: 101. 对称二叉树

思路

思路1：递归法。对于两颗树，对称的条件是：

• root1的左子树和root2的右子树对称

• root1的右子树和root2的左子树对称

• root1.Val == root2.Val

思路2：迭代法。整体思路与方法1类似，用一个队列存储两颗子树的节点，加入队列时两颗子树交叉按照左右右左的顺序添加，然后判断队列中相邻两个节点的值是否相等。

Code

代码1：

func isSymmetricV1(root *TreeNode) bool {
	if root == nil {
		return true
	}
	return symmetric(root.Left, root.Right)
}

func symmetric(root1 *TreeNode, root2 *TreeNode) bool {
	if root1 == nil && root2 == nil {
		return true
	}

	if root1 == nil || root2 == nil {
		return false
	}

	return symmetric(root1.Left, root2.Right) && symmetric(root1.Right, root2.Left) && root1.Val == root2.Val
}

代码2：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
	u, v := root, root
	queue := []*TreeNode{u, v}
	for len(queue) > 0 {
		u, v := queue[0], queue[1]
		queue = queue[2:]
		if u == nil && v == nil {
			continue
		}

		if u == nil || v == nil {
			return false
		}

		if u.Val != v.Val {
			return false
		}

		queue = append(queue, u.Left)
		queue = append(queue, v.Right)

		queue = append(queue, u.Right)
		queue = append(queue, v.Left)
	}

	return true
}