递归树对称性

Question

我编写了以下代码片段，以确定二叉树是否对称：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool symmetricityChecker(TreeNode* root, int level) {
        bool isValid=false;

        if(root==NULL)
            return true;

        if(level==1)
            isValid = root->left->val==root->right->val;

        if(root->left!=NULL && root->right!=NULL) {
            if(root->left->left!=NULL && root->right->right!=NULL)
                isValid = root->left->left->val==root->right->right->val;

            if(root->left->right!=NULL && root->right->left!=NULL)
                isValid = root->left->right->val==root->right->left->val;
        }

        return isValid && symmetricityChecker(root->left, level+1) && symmetricityChecker(root->right, level+1);
    }

    bool isSymmetric(TreeNode* root) {
        return symmetricityChecker(root, 0);
    }
};

我的目标是，在第1级，我检查根的左子和右子是否相等(因为在这个级别上只有一个根和它的两个子)。对于其余的所有级别，我检查root's left子级的right子级是否等于root's right子级的right子级，类似地，我检查root's left子级的right子级是否等于left的root的right子级。(这是这样的，因为在上一次递归调用中已经检查了根的直接左、右子级的对称性)。

我相信我的算法是正确的，但它正在产生不正确的结果。有人能善意地指出我的逻辑是否不正确，还是在实现中有错误？

编辑：，我测试了输入[1,2,2,3,4,4,3]的代码。我希望答案是true，但是得到一个false。因此，我不知道我的做法是否有逻辑上的缺陷。

Answer 1

错误的地方是你这么做的地方：

    return isValid && symmetricityChecker(root->left, level+1) && symmetricityChecker(root->right, level+1);

通过在单个子节点上调用symmetricityChecker，您期望子节点也是对称的，但这不应该是正确的。所以它会失败，因为子树2,3,4不对称，并且认为整个树是不对称的，即使这不是真的。

要递归地检查对称性，您必须保持两个节点(即左和右)作为您的状态，而不仅仅是一个。确认这两个节点是对称的之后，递归地检查它们的子节点，方法类似于您在嵌套的if条件下所做的检查。

另一种方法是编写BFS，并检查同一级别上的所有节点是否对称。这样，就应该像检查数组是否是对称的一样容易，因为在同一数组中，所有相同级别的节点都在彼此之间。

编辑:添加伪代码：

bool symmetricityChecker(left, right) {
    // Write the base case, check for nulls, corner cases, etc.
    if(left != right) return false
    return symmetricityChecker(left.left, right.right) &&
           symmetricityChecker(left.right, right.left)
}

在开始时，当您只有根时，使用根的子元素调用此方法。