首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【leetcode刷题】T114-对称二叉树

【leetcode刷题】T114-对称二叉树

作者头像
木又AI帮
发布2019-07-17 22:04:02
3890
发布2019-07-17 22:04:02
举报
文章被收录于专栏:木又AI帮木又AI帮

木又连续日更第66天(66/100)


木又的第114篇leetcode解题报告

二叉树类型第4篇解题报告

leetcode第101题:对称二叉树

https://leetcode-cn.com/problems/symmetric-tree/


【题目】

给定一个二叉树,检查它是否是镜像对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
    1
   / \
  2   2
   \   \
   3    3

说明:

如果你可以运用递归和迭代两种方法解决这个问题,会很加分。

【思路】

有一个比较直观的想法:层次遍历,得到每一层的节点,判断是否对称。所需的空间复杂度较高。

还有一个可行的想法:将左子树(或者右子树)进行翻转,再判断两子树是否完全相同。

其实不用这么麻烦,对于以某两个节点(node1和node2)为根节点的子树是否对称,首先判断node1和node2是否相同(是否都为NULL,或者值是否相同),再递归判断node1->left和node2->right是否相同,以及node1->right和node2->left是否相同。

【代码】

python版本

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        return self.issame(root.left, root.right)

    def issame(self, node1, node2):
        if (node1 and not node2) or (not node1 and node2):
            return False
        if (not node1 and not node2):
            return True
        if node1.val != node2.val:
            return False
        return self.issame(node1.left, node2.right) and self.issame(node1.right, node2.left)

C++版本

/**
 * Definition for a binary tree node.
 * 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 issame(root->left, root->right);
    }

    bool issame(TreeNode* node1, TreeNode* node2){
        if((!node1 && node2) || (node1 && !node2))
            return false;
        if(!node1 && !node2)
            return true;
        if(node1->val != node2->val)
            return false;
        return issame(node1->left, node2->right) && issame(node1->right, node2->left);
    }
};
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-07-12,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 木又AI帮 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档