leetcode-101：对称二叉树

题目

题目链接
给定一个二叉树，检查它是否是镜像对称的。

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

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

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

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

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

解题

比较推荐方法二和方法三

方法一： 广度优先搜索(BFS)(i)

python解法
利用层序遍历的方式，把每层的节点都放入到tmp中，不存在的节点用 None去代替。
如果该层全有结点的逆序和原来相同，那么就是对称的。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        queue = [root]
        while queue:
            tmp = []
            l = len(queue)
            for _ in range(l):
                cur = queue.pop(0)
                left,right = cur.left,cur.right
                if left:
                    queue.append(left)
                    tmp.append(left.val) 
                else:
                    tmp.append(None)
                if right:
                    queue.append(right)
                    tmp.append(right.val)
                else:
                    tmp.append(None)
            if tmp!=tmp[::-1]:
                return False
        return True

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

c++解法
c++中并不能使用NULL，因为c++中的NULL就是0，如果节点的值也为0就会出错。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        queue<TreeNode*> queue;
        queue.push(root);
        while(!queue.empty()){
            vector<int> tmp;
            int l= queue.size();
            for(int i=0;i<l;i++){
                TreeNode* cur=queue.front();
                queue.pop();
                TreeNode* left=cur->left;
                TreeNode* right=cur->right;
                if(left){
                    queue.push(left);
                    tmp.push_back(left->val);
                }
                else tmp.push_back(INT_MAX);
                if(right){
                    queue.push(right);
                    tmp.push_back(right->val);
                }
                else tmp.push_back(INT_MAX);
                
            }
            vector<int> tmp2(tmp);
            reverse(tmp2.begin(),tmp2.end());
            if(tmp!=tmp2){
                return false;
            }
        }
        return true;
    }
};
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
32
33
34
35

方法二：递归(DFS)

python解法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        def dfs(left,right):
            if not (left or right):
                return True
            if not (left and right):
                return False
            if left.val!=right.val:
                return False
            return dfs(left.left,right.right) and dfs(left.right,right.left)
        return dfs(root.left,root.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

c++解法

class Solution {
public:
    bool dfs(TreeNode* left,TreeNode* right){
        if(!(left||right)) return true;
        if(!(left&&right)) return false;
        if(left->val!=right->val) return false;
        return dfs(left->left,right->right)&&dfs(left->right,right->left);
    }
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return dfs(root->left,root->right);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

java解法

class Solution {
    boolean dfs(TreeNode L,TreeNode R){
        if(L==null&&R==null) return true;
        if(L==null||R==null) return false;
        if(L.val!=R.val) return false;
        return dfs(L.left,R.right)&&dfs(L.right,R.left);
    }
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        return dfs(root.left,root.right);
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

方法三：迭代(DFS)

这种写法，直接在queue中放入root.left,root.right,是因为判断对称，不用考虑头节点
python解法

class Solution(object):
	def isSymmetric(self, root):
		"""
		:type root: TreeNode
		:rtype: bool
		"""
		if not root or not (root.left or root.right):
			return True
		# 用队列保存节点	
		queue = [root.left,root.right]
		while queue:
			# 从队列中取出两个节点，再比较这两个节点
			left = queue.pop(0)
			right = queue.pop(0)
			# 如果两个节点都为空就继续循环，两者有一个为空就返回false
			if not (left or right):
				continue
			if not (left and right):
				return False
			if left.val!=right.val:
				return False
			# 将左节点的左孩子， 右节点的右孩子放入队列
			queue.append(left.left)
			queue.append(right.right)
			# 将左节点的右孩子，右节点的左孩子放入队列
			queue.append(left.right)
			queue.append(right.left)
		return True

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

c++解法

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        queue<TreeNode*> queue;
        queue.push(root->left);
        queue.push(root->right);
        while(!queue.empty()){
            TreeNode* left=queue.front();
            queue.pop();
            TreeNode* right=queue.front();
            queue.pop();
            if(!(left||right)) continue;
            if(!(left&&right)) return false;
            if(left->val!=right->val) return false;
            queue.push(left->left);
            queue.push(right->right);
            queue.push(left->right);
            queue.push(right->left);
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23