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

木又AI帮

发布于 2019-07-17 22:04:02

43800

代码可运行

文章被收录于专栏：木又AI帮木又AI帮

运行总次数：0

代码可运行

木又连续日更第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 删除

node.js