101. 对称二叉树

题意：

解题思路：

思路：
递归：O(n)
1. 首先判断t1->val == t2->val
2. 再判断，t1->left->val == t2->right->val, t1->right->val == t2->left->val
3. 终止条件为两棵树中一颗为空，或者已经到达了空节点；
BFS：采用队列来实现，思路跟递归差不多；时间复杂度是 O(n)
1. 先将根的左右节点入队
2. 弹出左右节点进行比较；如果相等，则将t1->left 和 t2->right放入对列；
3. 再将t1->right 和t2->left 放入队列；
4. 继续下一轮比较，直到子树为空退出；

PHP代码实现：

class Solution {
    /**
     * @param TreeNode $root
     * @return Boolean
     */
    function isSymmetric($root) {
        return $this->isSymmetricIterative($root);
       // return $this->isMirror($root, $root);
    }
    function isMirror($t1, $t2) {        
        if ($t1 == null && $t2 == null) return true;
        if ($t1 == null || $t2 == null) return false;
        return $t1->val == $t2->val && $this->isMirror($t1->left, $t2->right) &&
            $this->isMirror($t1->right, $t2->left);
    }
    function isSymmetricIterative($root) {
        if ($root == null) return true;
        $s = new SplStack;
        $s->push($root->left);
        $s->push($root->right);
        while (!$s->isEmpty()) {
            $s1 = $s->pop();
            $s2 = $s->pop();
            if ($s1 == null && $s2 == null) continue;
            if ($s1 == null || $s2 == null) return false;
            if ($s1->val != $s2->val) return false;
            $s->push($s1->left);
            $s->push($s2->right);
            $s->push($s1->right);
            $s->push($s2->left);
        }
        return true;
    }
}

GO代码实现：

/**
 * 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 isMirror(root, root)
}
func isMirror(left, right *TreeNode) bool {
    if left == nil && right == nil {
            return true
        }
        if left == nil || right == nil {
            return false
        }
        return left.Val == right.Val && isMirror(left.Left, right.Right) && isMirror(left.Right, right.Left)
}
func isMirrorIterate(left, right *TreeNode) bool {
    q := []*TreeNode{}
    q = append(q, left, right)
    for len(q) > 0 {
        n1, n2 := q[0], q[1]
        q = q[2:]
        if n1 == nil && n2 == nil {
            continue
        }
        if n1 == nil || n2 == nil {
            return false
        }
        if n1.Val != n2.Val {
            return false
        }
        q = append(q, n1.Left, n2.Right)
        q = append(q, n1.Right, n2.Left)
    }
    return true
}