[leetcode]-二叉树的对称性(镜像对称)判别

题目描述

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

  1
 / \
2   2
 \   \
 3

算法实现

如果同时满足下面的条件，两个树互为镜像：

它们的两个根结点具有相同的值。
每个树的右子树都与另一个树的左子树镜像对称。

递归版(php)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {

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

    function isMirror($node1, $node2) {
        if ($node1 == null && $node2 == null) return true;
        if ($node1 == null || $node2 == null) return false;
        return ($node1->val == $node2->val)
            && $this->isMirror($node1->right, $node2->left)
            && $this->isMirror($node1->left, $node2->right);
    }
}

迭代版(php)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    public $q1 = [];
    public $q2 = [];
    /**
     * @param TreeNode $root
     * @return Boolean
     */
    function isSymmetric($root) {
    	if($root==null){
            return true;
        }
        $this->q1[] = $root->left;
        $this->q2[] = $root->right;
        while(!empty($this->q1)&&!empty($this->q2)){
            $t1 = array_shift($this->q1);
            $t2 = array_shift($this->q2);
            if($t1==null&&$t2==null){
                continue;
            }
            if($t1==null||$t2==null||$t1->val!=$t2->val){
                return false;
            }
            $this->q1[] = $t1->left;
            $this->q1[] = $t1->right;
            $this->q2[] = $t2->right;
            $this->q2[] = $t2->left;
        }
        return count($this->q1)==count($this->q2);
    }
}

参考

对称二叉树