0101. 对称二叉树

题目地址(101. 对称二叉树)

题目描述

1
给定一个二叉树,检查它是否是镜像对称的。
2
3
4
5
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
6
7
1
8
/ \
9
2 2
10
/ \ / \
11
3 4 4 3
12
13
14
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
15
16
1
17
/ \
18
2 2
19
\ \
20
3 3
21
22
23
进阶:
24
25
你可以运用递归和迭代两种方法解决这个问题吗?
Copied!

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节
  • bloomberg
  • linkedin
  • microsoft

前置知识

思路

看到这题的时候,我的第一直觉是 DFS。然后我就想:如果左子树是镜像,并且右子树也是镜像,是不是就说明整体是镜像?。经过几秒的思考, 这显然是不对的,不符合题意。
很明显其中左子树中的节点会和右子树中的节点进行比较,我把比较的元素进行了颜色区分,方便大家看。
这里我的想法是:遍历每一个节点的时候,如果我都可以通过某种方法知道它对应的对称节点是谁,这样的话我直接比较两者是否一致就行了。
因此想法是两次遍历,第一次遍历的同时将遍历结果存储到哈希表中,然后第二次遍历去哈希表取。这种方法可行,但是需要 N 的空间(N 为节点总数)。我想到如果两者可以同时进行遍历,是不是就省去了哈希表的开销。
如果不明白的话,我举个简单例子:
1
给定一个数组,检查它是否是镜像对称的。例如,数组 [1,2,2,3,2,2,1] 是对称的。
Copied!
如果用哈希表的话大概是:
1
seen = dict()
2
for i, num in enumerate(nums):
3
seen[i] = num
4
for i, num in enumerate(nums):
5
if seen[len(nums) - 1 - i] != num:
6
return False
7
return True
Copied!
而同时遍历的话大概是这样的:
1
l = 0
2
r = len(nums) - 1
3
4
while l < r:
5
if nums[l] != nums[r]: return False
6
l += 1
7
r -= 1
8
return True
Copied!
其实更像本题一点的话应该是从中间分别向两边扩展 😂

代码

代码支持:C++, Java, Python3
C++ Code:
1
/**
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
class Solution {
11
public:
12
bool isSymmetric(TreeNode* root) {
13
return root==NULL?true:recur(root->left, root->right);
14
}
15
16
bool recur(TreeNode* l, TreeNode* r)
17
{
18
if(l == NULL && r==NULL)
19
{
20
return true;
21
}
22
// 只存在一个子节点 或者左右不相等
23
if(l==NULL || r==NULL || l->val != r->val)
24
{
25
return false;
26
}
27
28
return recur(l->left, r->right) && recur(l->right, r->left);
29
}
30
};
Copied!
Java Code:
1
/**
2
* Definition for a binary tree node.
3
* public class TreeNode {
4
* int val;
5
* TreeNode left;
6
* TreeNode right;
7
* TreeNode(int x) { val = x; }
8
* }
9
*/
10
class Solution {
11
public boolean isSymmetric(TreeNode root) {
12
if(root == null)
13
{
14
return true;
15
}
16
else{
17
return recur(root.left, root.right);
18
}
19
// return root == null ? true : recur(root.left, root.right);
20
}
21
22
public boolean recur(TreeNode l, TreeNode r)
23
{
24
if(l == null && r==null)
25
{
26
return true;
27
}
28
// 只存在一个子节点 或者左右不相等
29
if(l==null || r==null || l.val != r.val)
30
{
31
return false;
32
}
33
34
return recur(l.left, r.right) && recur(l.right, r.left);
35
}
36
}
Copied!
Python3 Code:
1
class Solution:
2
def isSymmetric(self, root: TreeNode) -> bool:
3
def dfs(root1, root2):
4
if root1 == root2 == None: return True
5
if not root1 or not root2: return False
6
if root1.val != root2.val: return False
7
return dfs(root1.left, root2.right) and dfs(root1.right, root2.left)
8
if not root: return True
9
return dfs(root.left, root.right)
Copied!
复杂度分析
  • 时间复杂度:$O(N)$,其中 N 为节点数。
  • 空间复杂度:递归的深度最高为节点数,因此空间复杂度是 $O(N)$,其中 N 为节点数。
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。