[Leetcode]101. Symmetric Tree(C++)

题目描述

题目链接：101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

例子

例子 1

Input: [1,2,2,3,4,4,3] Output: true

例子 2

Input: [1,2,2,null,3,null,3] Output: false

解题思路

利用递归可以比较方便求解，只需要判断根节点的左右两棵子树left 和 right 是否完全对称，判断方法如下：

两子树的根节点都为空，返回 true
其中一子树的根节点为空，返回 false
两根节点的值不同，返回 false
对 left->left， right->right 和 left->right, right->left 做同样判断

代码如下：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return isSymmetric(root->left, root->right);
    }

private:
    bool isSymmetric(TreeNode* left, TreeNode* right) {
        if (!left && !right) return true;
        if (!left || !right) return false;
        if (left->val != right->val) return false;
        return isSymmetric(left->left, right->right) &&
               isSymmetric(left->right, right->left);
    }
};

时间复杂度: O(n)
空间复杂度: O(h)

GitHub 代码同步地址： 101.SymmetricTree.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions