0%

[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

解题思路

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

  • 两子树的根节点都为空,返回 true
  • 其中一子树的根节点为空,返回 false
  • 两根节点的值不同,返回 false
  • left->left, right->rightleft->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