【算法题】对称的二叉树

这题让判断二叉树是否对称，如果只有一个节点是没法判断的，所以根节点不需要判断，只需要判断两个子节点的值是否相等，但子节点的子节点也需要判断，我们可以使用递归的方式，判断的原则是：

• 左子节点的左子节点和右子节点的右子节点比较。
• 左子节点的右子节点和右子节点的左子节点比较。

如下图所示：

    public boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot == null)
            return true;
        // 从两个子节点开始判断
        return dfs(pRoot.left, pRoot.right);
    }

    private boolean dfs(TreeNode left, TreeNode right) {
        // 两个节点都为空，返回true
        if (left == null && right == null)
            return true;
        // 如果当前节点只有一个子节点或者有两个子节点，但两个子节点的值不相同，直接返回false
        if (left == null || right == null || left.val != right.val)
            return false;
        // 左子节点的左子节点和右子节点的右子节点比较，左子节点的右子节点和右子节点的左子节点比较
        return dfs(left.left, right.right) && dfs(left.right, right.left);
    }

public:
    bool isSymmetrical(TreeNode *pRoot) {
        if (pRoot == nullptr)
            return true;
        // 从两个子节点开始判断
        return dfs(pRoot->left, pRoot->right);
    }

    bool dfs(TreeNode *left, TreeNode *right) {
        // 两个节点都为空，返回true
        if (left == nullptr && right == nullptr)
            return true;
        // 如果当前节点只有一个子节点或者有两个子节点，但两个子节点的值不相同，直接返回false
        if (left == nullptr || right == nullptr || left->val != right->val)
            return false;
        // 左子节点的左子节点和右子节点的右子节点比较，左子节点的右子节点和右子节点的左子节点比较
        return dfs(left->left, right->right) && dfs(left->right, right->left);
    }

各大厂算法面试题已经整理好了，请看这里：《算法专栏》