每天进步一点点🤏

对称二叉树

  • 950 字

对称二叉树

题目

1
2
3
4
5
6
7
8
9
给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false

解法

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
思路:
将二叉树分为左右两个树,遍历两树,对比左树的左节点和右树的右节点,对比左树的右节点和右树的左节点,
节点值相同,且都不存在子节点时(代表递归到了最后),才返回true,其余情况返回false

代码:
/**
 * @param TreeNode $root
 *
 * @return Boolean
 */
function isSymmetric($root)
{
    return $this->isSymmetricalTree($root->left,$root->right);
}

function isSymmetricalTree($p, $q)
{
    //当前节点的值不同,返回false
    if ($p->val !== $q->val) {
        return false;
    }

    //当前节点不存在左右子节点,且节点的值相同,返回true
    if (
        !$p->right && !$p->left &&
        !$q->right && !$q->left
    ) {
        return true;
    }

    //当前节点的值相同且存在子节点,使用对称子节点去递归对比
    return $this->isSymmetricalTree($p->right, $q->left) &&
        $this->isSymmetricalTree($p->left, $q->right);
}