Keshawn_lu's Blog

Leetcode 101. 对称二叉树

字数统计: 248阅读时长: 1 min
2020/05/31 Share

题目简介:

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

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

1
2
3
4
5
    1
/ \
2 2
/ \ / \
3 4 4 3

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

1
2
3
4
5
  1
/ \
2 2
\ \
3 3

思路:

运用递归,由于是镜像对称,所以判定左树的左子树和右树的右子树,左树的右子树和右树的左子树是否相等即可。

tips:

  • 两结点均为空时,相等
  • 只有一结点为空时,不相等

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:

bool dfs(TreeNode* left_tree, TreeNode* right_tree){

if(!left_tree && !right_tree)
return true;
if(!left_tree || !right_tree)
return false;

if(left_tree -> val != right_tree -> val)
return false;

return dfs(left_tree -> left, right_tree -> right)
&& dfs(left_tree -> right, right_tree -> left);
}

bool isSymmetric(TreeNode* root) {

return dfs(root, root);
}
};

最后祝贺自己五月打卡成功!!!

CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: