Skip to content

LeetCode 101 对称二叉树#

目录#

1. 题目描述#

1.1. Limit#

Time Limit: 1000 ms

Memory Limit: 131072 kB

1.2. Problem Description#

给定一个二叉树，检查它是否是镜像对称的。

1.5. Sample Input 1#

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
    1
   / \
  2   2
 / \ / \
3  4 4  3

1.6. Sample Output 1#

true

1.5. Sample Input 2#

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
    1
   / \
  2   2
   \   \
   3    3

1.6. Sample Output 2#

false

1.8. Source#

LeetCode 101 对称二叉树

2. 解读#

DFS，先判断节点是否为空，然后分别比较左右节点的值是否相等。这里需要注意的是根节点为空时是对称的。

3. 代码#

class Solution {
public:
    bool isNodeSymmetric(TreeNode* p, TreeNode* q)
    {
        bool leftFalg = false, rightFlag = false;
        // 若其一为空
        if (p == nullptr || q == nullptr) {
            // 判断是否都为空
            if (p == q) {
                return true;
            } else {
                return false;
            }

        } else {
            // 若不为空
            if (p->val != q->val) {
                // 若值不相等，返回false
                return false;
            }
            // 若值相等，继续判定左右节点
            leftFalg = isNodeSymmetric(p->left, q->right);
            rightFlag = isNodeSymmetric(p->right, q->left);

            if (leftFalg && rightFlag) {
                return true;
            } else {
                return false;
            }
        }
    }

    bool isSymmetric(TreeNode* root)
    {
        if (root == nullptr){
            return true;
        }else{
            return isNodeSymmetric(root->left, root->right);
        }
    }
};

联系邮箱：curren_wong@163.com

CSDN：https://me.csdn.net/qq_41729780

知乎：https://zhuanlan.zhihu.com/c_1225417532351741952

公众号：复杂网络与机器学习

欢迎关注/转载，有问题欢迎通过邮箱交流。

二维码

Back to top