美文网首页
101. Symmetric Tree

101. Symmetric Tree

作者: YellowLayne | 来源:发表于2017-06-19 10:48 被阅读0次

    1.描述

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

    For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

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

    But the following [1,2,2,null,3,null,3] is not:

        1
       / \
      2   2
       \   \
       3    3
    

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

    2.方法一

    2.1分析

    将右子树反转,然后判断左子树和反转后的右子树是否相同。

    2.2代码

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    
    void reversal(struct TreeNode* root) {
        if (NULL == root) return ;
        reversal(root->left);
        reversal(root->right);
        struct TreeNode* tmp;
        tmp = root->left;
        root->left = root->right;
        root->right = tmp;
    }
    
    bool isSameTree(struct TreeNode* tree1, struct TreeNode* tree2) {
        if (NULL == tree1 && NULL == tree2) return true;
        if (NULL == tree1 || NULL == tree2) return false;
        if (tree1->val != tree2->val) return false;
        bool left = isSameTree(tree1->left, tree2->left);
        bool right = isSameTree(tree1->right, tree2->right);
        return left && right;
    }
     
    bool isSymmetric(struct TreeNode* root) {
        if (NULL == root) return true;
        if (NULL == root->left && NULL == root->right) return true;
        if (NULL == root->left || NULL == root->right) return false;
        reversal(root->right);
        return isSameTree(root->left, root->right);
    }
    

    3.方法二

    3.1分析

    层次遍历二叉树,判断每层的元素是否对称。

    3.2代码

    4.方法三

    4.1分析

    简单递归

    4.2代码

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
     
    bool isSymmetricRL(struct TreeNode* root1, struct TreeNode* root2) {
        if (NULL == root1 && NULL == root2) return true;
        if (NULL == root1 || NULL == root2) return false;
        if (root1->val != root2->val) return false;
        return isSymmetricRL(root1->left, root2->right) && isSymmetricRL(root1->right, root2->left);
    }
    
    bool isSymmetric(struct TreeNode* root) {
        if (NULL == root) return true;
        return isSymmetricRL(root->left, root->right);
    }
    

    相关文章

      网友评论

          本文标题:101. Symmetric Tree

          本文链接:https://www.haomeiwen.com/subject/obrgqxtx.html