题目 LC101. 对称二叉树

解题思路

首先二叉树要满足以下条件才是对称的二叉树：

  1. 由外向内的值相同
1
2
3
4
5
6
7
			1
	2				2
3		4		4		3

[2, 2]
[3, 4, 3, 4]
类似一个双指针，不断向内收缩同时对比是否相等
  1. 左右子树深度相同，也就是左右子树节点数相同

我们模拟这个由外到内的过程就能判断二叉树是不是对称的

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        q = deque()
        q.append(root.left)
        q.append(root.right)
        while q:
            # 左节点和右节点
            leftNode = q.popleft()
            rightNode = q.popleft()
            
            # 两个节点为空
            if (not rightNode) and (not leftNode):
                continue
            
            if (not rightNode) or (not leftNode) or (leftNode.val != rightNode.val):
                return False
            # 左节点的左孩子   右节点右孩子
            q.append(leftNode.left)
            q.append(rightNode.right)
            # 左节点右孩子    右节点左孩子
            q.append(leftNode.right)
            q.append(rightNode.left)
        return True

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);
        while (!q.empty()) {
            TreeNode* leftNode = q.front(); q.pop();
            TreeNode* rightNode = q.front(); q.pop();
            // 节点都是空
            if (!leftNode && !rightNode) continue;
            // 一个节点为空一个不为空，或者两个节点值不同
            if ((!leftNode || !rightNode) || leftNode->val != rightNode->val) return false;
            // 左节点左孩子 右节点右孩子
            q.push(leftNode->left);
            q.push(rightNode->right);
            // 左节点右孩子 右节点左孩子
            q.push(leftNode->right);
            q.push(rightNode->left);
        }
        return true;
    }
};