XTAO's Tech Blog
0%

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

发表于 更新于 分类于 ， 评论数：
909 1 分钟

题目描述

题目链接：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 做同样判断

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

推荐文章