对称的二叉树（Python and C++解法）
2021-04-25 07:27
标签：题目 pen ack 迭代 常用 基础 默认 push public 给定一个二叉树，检查它是否是镜像对称的。 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 1 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1 来源：力扣（LeetCode） 如果一个树的左子树与右子树镜像对称，那么这个树是对称的。 两个树互为镜像需要满足：它们的两个根结点具有相同的值；每个树的右子树都与另一个树的左子树镜像对称。 可以递归解决，通过同步移动两个指针的方法来遍历这棵树，p指针和q指针一开始都指向这棵树的根，随后p右移时，q左移，p左移时，q右移。每次检查当前p和q节点的值是否相等，如果相等再判断左右子树是否对称。 也可以迭代解决，首先我们引入一个队列，这是把递归改写成迭代的常用方法。初始化时需要把根节点入队 两次。每次提取两个结点并比较它们的值（如果树对称，队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按对称的顺序插入队列中。当队列为空时，或者检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。 对称的二叉树（Python and C++解法） 标签：题目 pen ack 迭代 常用 基础 默认 push public 原文地址：https://www.cnblogs.com/kongzimengzixiaozhuzi/p/13260006.html题目：
/ \
2 2
/ \ / \
3 4 4 3
/ \
2 2
\ \
3 3
链接：https://leetcode-cn.com/problems/symmetric-tree思路：
Python递归解法：
1 class TreeNode:
2 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
6
7 class Solution:
8 def isSymmetric(self, root: TreeNode) -> bool:
9 return self.check(root, root)
10
11 def check(self, nodeP, nodeQ):
12 if not nodeP and not nodeQ: # 如果同时遇到空节点
13 return True
14 if not nodeP or not nodeQ: # 因为上面一次判断，已经排除!nodeP and !nodeQ的情况
15 return False
16 if nodeP.val == nodeQ.val:
17 return self.check(nodeP.left, nodeQ.right) and self.check(nodeP.right, nodeQ.left)
18 return False
Python迭代解法：
1 class TreeNode:
2 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
6
7 class Solution:
8 def isSymmetric(self, root: TreeNode) -> bool:
9 return self.check(root, root)
10
11 def check(self, nodeP, nodeQ):
12 queue = []
13 queue.append(nodeP)
14 queue.append(nodeQ)
15
16 while len(queue):
17 nodeP = queue.pop(0) # python的pop默认返回列表最后一个元素
18 nodeQ = queue.pop(0)
19 if not nodeP and not nodeQ:
20 continue
21 if (not nodeP or not nodeQ) or nodeP.val != nodeQ.val:
22 return False
23 queue.append(nodeP.left)
24 queue.append(nodeQ.right)
25
26 queue.append(nodeP.right)
27 queue.append(nodeQ.left)
28 return True
C++递归解法：
1 struct TreeNode {
2 int val;
3 TreeNode *left;
4 TreeNode *right;
5 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
6 };
7
8 class Solution {
9 public:
10 bool check(TreeNode *nodeP, TreeNode *nodeQ) {
11 if (!nodeP && !nodeQ)
12 return true;
13 if (!nodeP || !nodeQ)
14 return false;
15 if (nodeP->val == nodeQ->val)
16 return check(nodeP->left, nodeQ->right) && check(nodeP->right, nodeQ->left);
17 return false; // 前面都是if,此处必须有返回
18 }
19
20 bool isSymmetric(TreeNode* root) {
21 return check(root, root);
22 }
23 };
C++迭代解法：
1 struct TreeNode {
2 int val;
3 TreeNode *left;
4 TreeNode *right;
5 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
6 };
7
8 class Solution {
9 public:
10 bool check(TreeNode *nodeP, TreeNode *nodeQ) {
11 queue
文章标题：对称的二叉树（Python and C++解法）
文章链接：http://soscw.com/index.php/essay/79303.html