101. 对称二叉树

方法一、递归法

思路

左右子树是否对称？

1. 值是否相同；
2. 左子树的左子树和右子树的右子树是否对称；
3. 左子树的右子树和右子树的左子树是否对称

复杂度

时间复杂度：O(n)

空间复杂度：O(n)

代码

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @return Boolean
     */
    function isSymmetric($root) {
        return $this->check($root, $root);
    }

    /**
     * 判断左右子树是否对称
     */
    function check($p, $q)
    {
        if(!$p && !$q) return true;
        if(!$p || !$q) return false;

        // 左右子树是否对称？
        // 1. 值是否相同；
        // 2. 左子树的左子树和右子树的右子树是否对称；
        // 3. 左子树的右子树和右子树的左子树是否对称
        return ($p->val == $q->val) && $this->check($p->left, $q->right) && $this->check($p->right, $q->left);
    }
}

方法二、非递归法

思路

递归改为非递归法，借助队列来实现。

让左子树的左子树和右子树的右子树紧挨着入队，出队时进行比较；

让左子树的右子树和右子树的左子树紧挨着入队，出队时进行比较。

复杂度

时间复杂度：O(n)

空间复杂度：O(n)

代码

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @return Boolean
     */
    function isSymmetric($root) {
        $list = [];
        $list[] = $root;
        $list[] = $root;
        while(count($list) > 0) {
            $p = array_shift($list);
            $q = array_shift($list);

            if($p == null && $q == null) continue;

            if(($p == null) || ($q == null) || ($p->val != $q->val)) return false;

            $list[] = $p->left;
            $list[] = $q->right;

            $list[] = $p->right;
            $list[] = $q->left;
        }

        return true;
    }
}