LeetCode 101 Symmetric Tree(对称树)(*)

简介: 版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50554857 翻译给定一个二叉树,检查它是否是它本身的镜像(也就是说,中心对称)。
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50554857

翻译

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

例如,这个二叉树是对称的:
    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.

分析

其实吧,这道题和下面这道题的思路非常的类似,都是从上向下不断的遍历,只不过是比较的对象不一样而已。

LeetCode 110 Balanced Binary Tree(平衡二叉树)(*)

一开始我写了下面这段代码,不过后来发现错了,镜像不是这么回事……下面的代码是每个节点的左右子节点对称,而镜像是对于整个树而言的一种对称。所以继续改改改……

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天前
|
存储 SQL 算法
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
|
5天前
|
存储 算法 数据可视化
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
|
9天前
|
搜索推荐 Java
单源最短路(只有一个起点)bfs,多源BFS,目录力扣675.为高尔夫比赛砍树,多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量
单源最短路(只有一个起点)bfs,多源BFS,目录力扣675.为高尔夫比赛砍树,多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量
|
9天前
|
算法 Java Go
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
5 0
|
17天前
|
算法 C语言 容器
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(下)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
31 7
|
17天前
|
C语言
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(中)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
25 1
|
17天前
|
算法 C语言 C++
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(上)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
16 1
|
23天前
LeetCode——572—— 另一棵树的子树
LeetCode——572—— 另一棵树的子树
|
23天前
LeetCode——101——对称二叉树
LeetCode——101——对称二叉树
44 12