【LeetCode算法】第101题：对称二叉树

目录

一、题目描述

二、初次解答

三、官方解法

四、总结

一、题目描述

二、初次解答

1. 思路：递归判定左子树和右子树是否对称。用一个新函数sym来递归判定左子树和右子树是否对称。该函数细节：判定当前传入的两个根节点是否为空，若均为空则返回true，若只有其中一个为空则返回false，若两个根节点的值不同则返回false，否则递归判断根节点1的左子树与根节点2的右子树是否相同并判断根节点1的右子树与根节点2的左子树是否相同。

2. 代码：

bool sym(struct TreeNode* root1, struct TreeNode* root2){
    if(!root1 && !root2)
        return true;
    if(!root1 || !root2)
        return false;
    if(root1->val != root2->val)
        return false;
    return sym(root1->left, root2->right) && sym(root1->right, root2->left);
}

bool isSymmetric(struct TreeNode* root) {
    return sym(root->left, root->right);
}

3. 优点：仅遍历一遍，时间复杂度为O(n)。

4. 缺点：采用了递归，空间复杂度为O(n)。

三、官方解法

官方解法一与上述方法相同。官方解法二采用迭代方式但需要手动维护队列空间，时间复杂度与空间复杂度与解法一相同，但是代码量更大，因此此处不展开说明。

四、总结

判定二叉树左右子树是否对称，可以递归判定根节点的左子树和右子树是否对称。