LeetCode 101 Symmetric Tree（对称树）（*）

翻译

给定一个二叉树，检查它是否是它本身的镜像（也就是说，中心对称）。

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

1
/ \
2   2
\   \
3    3

原文

Given a binary tree, check whether it is a mirror of itself
(ie, symmetric around its center).

For example, this binary tree is symmetric:
1
/ \
2   2
/ \ / \
3  4 4  3

But the following is not:
1
/ \
2   2
\   \
3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

分析

bool isSymmetric(TreeNode* root) {
if (!root || (!root->left && !root->right)) return true;
else if (!root->left || !root->right) return false;
if (root->left->val != root->right->val)
return false;
else if (!isSymmetric(root->left) || !isSymmetric(root->right)) return false;
return true;
}

bool  isSymmetricIter(TreeNode* r1, TreeNode* r2) {
if (!r1 && !r2)  return true;
else if (!r1 || !r2) return false;
if ((!r1->left && !r2->right && !r1->right && !r2->left)) return true;
if ((r1->left && r2->right)) {
if (r1->left->val != r2->right->val)
return false;
}
else if (!r1->left && !r2->right) {}
else return false;
if ((r1->right && r2->left)) {
if (r1->right->val != r2->left->val)
return false;
}
else if (!r1->right && !r2->left) {}
else return false;

if (!isSymmetricIter(r1->left, r2->right) || !isSymmetricIter(r1->right, r2->left)) return false;
return true;
}

bool isSymmetric(TreeNode* root) {
if (!root) return true;
else if (!root->left && !root->right) return true;
else if (!root->left || !root->right) return false;
else if (root->left->val != root->right->val) return false;
return isSymmetricIter(root->left, root->right);
return isSymmetricIter(root->left, root->right);
}

bool  isSymmetricIter(TreeNode* r1, TreeNode* r2) {
if (!r1 && !r2)  return true;
else if (!r1 || !r2) return false;
if (!r1->left && !r2->right && !r1->right && !r2->left) return true;

if ((r1->left && r2->right)) {
if (r1->left->val != r2->right->val)
return false;
}
else if (!(!r1->left && !r2->right)) return false;
if ((r1->right && r2->left)) {
if (r1->right->val != r2->left->val)
return false;
}
else if (!(!r1->right && !r2->left)) return false;

if (!isSymmetricIter(r1->left, r2->right) || !isSymmetricIter(r1->right, r2->left)) return false;
return true;
}

bool isSymmetric(TreeNode* root) {
if (!root) return true;
return isSymmetricIter(root, root);
}

|
5天前
|
SQL 算法 数据可视化
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
5 0
|
5天前
|

LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
6 0
|
5天前
|

python多种算法对比图解实现 验证二叉树搜索树【力扣98】
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
8 0
|
9天前
|

15 0
|
9天前
|

【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
5 0
|
17天前
|

31 7
|
17天前
|
C语言

25 1
|
17天前
|

16 1
|
23天前
LeetCode——572—— 另一棵树的子树
LeetCode——572—— 另一棵树的子树
9 0
|
23天前
LeetCode——101——对称二叉树
LeetCode——101——对称二叉树
44 12