《剑指Offer》-28.对称的二叉树

题干

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它就是对称的。例如在下图的三棵二叉树中，第一棵二叉树是对称的，而另外两棵不是。

第一棵

graph TD
8-->B[6]
8-->C[6]
B-->D[5]
B-->E[7]
C-->F[7]
C-->G[5]

第二棵

graph TD
8-->B[6]
8-->C[9]
B-->D[5]
B-->E[7]
C-->F[7]
C-->G[5]

第三棵

graph TD
A[7]-->B[7]
A[7]-->C[7]
B-->D[7]
B-->E[7]
C-->F[7]

解题思路

思路一：

根据题干我们可以想到第一种解决方案，就是先求得二叉树的镜像，然后遍历两棵二叉树，看每一步中节点值是否相同。

思路二

树的根节点是相同的，对于子树只需要判断左子树的左孩子是否等于右子树的右孩子，左子树的右孩子是否等于右子树的左孩子，如果出现不同，则表示不是对称的。

代码实现

<?php

class TreeNode
{
    private $val;
    private $left;
    private $right;

    public function __set($name, $value)
    {
        $this->$name = $value;
    }

    public function __get($name)
    {
        return $this->$name;
    }
}

function getTree()
{
    $node1 = new TreeNode();
    $node1->val = 7;
    $node2 = new TreeNode();
    $node2->val = 7;
    $node3 = new TreeNode();
    $node3->val = 7;
    $node1->left = $node2;
    $node1->right = $node3;
    $node4 = new TreeNode();
    $node4->val = 7;
    $node5 = new TreeNode();
    $node5->val = 7;
    $node2->left = $node4;
    $node2->right = $node5;
    $node6 = new TreeNode();
    $node6->val = 7;
//    $node7 = new TreeNode();
//    $node7->val = 7;
    $node3->left = $node6;
//    $node3->right = $node7;

    return $node1;
}

function isSymmetrical($tree)
{
    return checkTreeIsSymmetrical($tree, $tree);
}

function checkTreeIsSymmetrical($tree1, $tree2)
{
    if ($tree1 == null && $tree2 == null) {
        return true;
    }
    if ($tree1 == null || $tree2 == null) {
        return false;
    }
    if ($tree1->val != $tree2->val){
        return false;
    }
    return checkTreeIsSymmetrical($tree1->left, $tree2->right)
        && checkTreeIsSymmetrical($tree1->right, $tree2->left);

}

$tree = getTree();

var_dump(isSymmetrical($tree));