2017年11月 – Tamarous

class Solution {
    public:
        bool isSymmetric(TreeNode *root) {
            if (root == NULL) {
                return true;
            }
            return isSymmetricHelper(root->left, root->right);
        }
    private:
        bool isSymmetricHelper(TreeNode *p,  TreeNode *q) {
            if (!p && !q) {
                return true;
            }
            if (p == NULL || q == NULL) {
                return false;
            }
            return (p->val == q->val) && isSymmetricHelper(p->left, q->right) && isSymmetricHelper(p->right, q->left);
        }
    };

class Solution {

public:

bool isSymmetric(TreeNode *root) {

if (root == NULL) {

return true;

}

return isSymmetricHelper(root->left, root->right);

}

private:

bool isSymmetricHelper(TreeNode *p, TreeNode *q) {

if (!p && !q) {

return true;

}

if (p == NULL || q == NULL) {

return false;

}

return (p->val == q->val) && isSymmetricHelper(p->left, q->right) && isSymmetricHelper(p->right, q->left);

}

};

今天刷剑指 offer，发现这道题还有另一种解法：首先定义另一种前序遍历A，也就是访问过父节点后，先遍历右子节点再遍历左子节点。那么一棵对称二叉树的A遍历和它的正常前序遍历结果是一样的。根据这种思路，可以写出如下的算法：

class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        return isSymmetrical(root,root);
    }    
    bool isSymmetrical(TreeNode *root1, TreeNode *root2) {
        if (root1 == NULL && root2 == NULL) {
            return true;
        }
        if (root1 == NULL || root2 == NULL) {
            return false;
        }
        if (root1->val != root2->val) {
            return false;
        }
        return isSymmetrical(root1->left, root2->right) && isSymmetrical(root1->right, root2->left);
    }
};

class Solution {

public:

bool isSymmetric(TreeNode *root) {

return isSymmetrical(root,root);

}

bool isSymmetrical(TreeNode *root1, TreeNode *root2) {

if (root1 == NULL && root2 == NULL) {

return true;

}

if (root1 == NULL || root2 == NULL) {

return false;

}

if (root1->val != root2->val) {

return false;

}

return isSymmetrical(root1->left, root2->right) && isSymmetrical(root1->right, root2->left);

}

};