[LeetCode] Symmetric Tree 判断对称树

简介:

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.

判断二叉树是否是平衡树,比如有两个节点n1, n2,我们需要比较n1的左子节点的值和n2的右子节点的值是否相等,同时还要比较n1的右子节点的值和n2的左子结点的值是否相等,以此类推比较完所有的左右两个节点。我们可以用递归和迭代两种方法来实现,写法不同,但是算法核心都一样。

递归方法 (Recursive Solution):

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        if (!root) return true;
        return isSymmetric(root->left, root->right);
    }
    bool isSymmetric(TreeNode *left, TreeNode *right) {
        if (!left && !right) return true;
        if (left && !right || !left && right || left->val != right->val) return false;
        return isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left);
    }
    
};

迭代方法 (Iterative Solution):

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        if (!root) return true;
        queue<TreeNode*> q1, q2;
        q1.push(root->left);
        q2.push(root->right);
        
        while (!q1.empty() && !q2.empty()) {
            TreeNode *node1 = q1.front();
            TreeNode *node2 = q2.front();
            q1.pop();
            q2.pop();
            if((node1 && !node2) || (!node1 && node2)) return false;
            if (node1) {
                if (node1->val != node2->val) return false;
                q1.push(node1->left);
                q1.push(node1->right);
                q2.push(node2->right);
                q2.push(node2->left);
            }
        }
        return true;
    }
};

本文转自博客园Grandyang的博客,原文链接:[LeetCode] Symmetric Tree 判断对称树

,如需转载请自行联系原博主。

相关文章
|
27天前
|
算法 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
34 7
|
1月前
LeetCode——101——对称二叉树
LeetCode——101——对称二叉树
48 12
|
27天前
|
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
27 1
|
27天前
|
算法 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
20 1
|
15天前
|
SQL 算法 数据可视化
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
|
15天前
|
存储 SQL 算法
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
|
15天前
|
存储 算法 数据可视化
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
|
19天前
|
搜索推荐 Java
单源最短路(只有一个起点)bfs,多源BFS,目录力扣675.为高尔夫比赛砍树,多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量
单源最短路(只有一个起点)bfs,多源BFS,目录力扣675.为高尔夫比赛砍树,多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量
|
19天前
|
算法 Java Go
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
8 0
|
1月前
LeetCode——572—— 另一棵树的子树
LeetCode——572—— 另一棵树的子树