Skip to content

Latest commit

 

History

History
135 lines (116 loc) · 4.56 KB

58.对称的二叉树.md

File metadata and controls

135 lines (116 loc) · 4.56 KB
Raw

58.对称的二叉树

题目描述

  • 请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

 

解题思路

如果根结点的左子树是右子树的镜像的话就是对称的。试了一下，牛客网上测试时空树也应该输出true。

  • 思路一，递归。另写一个函数判断一棵树A是否是另一颗树B的镜像，判断规则是结点A和B的值相等，且A的左结点是B的右结点的镜像，A的右结点是B左结点的镜像。
  • 思路二，迭代。使用左子树前序遍历（中左右）右子树中右左的方式，结合队列或者栈。
    • 两个队列。创建两个队列queueA和queueB，先将根结点的左右子结点A和B分别入各自的队列，当队同时不为空的时候两个队列各弹出一个结点a和b，如果a和b的val相等的话就把a的左右结点依次入队，b的右左结点依次入队，注意两边入队的顺序是对称的，如果a和b同时为NULL的话就继续下一次循环，只有一个为NULL的话直接返回false。最后两个队列同时空的话就是true，否则就是false。
    • 两个栈，和队列差不多。创建两个栈stackA和stackB，先将根结点的左右子结点A和B分别入各自的栈，当栈同时不为空的时候两个栈各弹出一个结点a和b，如果a和b的val相等的话就把a的左右结点依次入栈，b的右左结点依次入栈，注意两边入栈的顺序是对称的；另外如果a和b同时为NULL的话就继续下一次循环，只有一个为NULL的话直接返回false。最后两个栈0同时空的话就是true，否则就是false。

 

代码

  • 思路一，递归（推荐，简洁快速）
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
private:
    bool isMirror(TreeNode* A, TreeNode* B){
    if(A==NULL && B==NULL) return true;
    if(A==NULL || B==NULL) return false;
    if(A->val != B-> val) return false;
    return isMirror(A->left, B->right) && isMirror(A->right, B->left);
}
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(pRoot==NULL) return true;
        return isMirror(pRoot->left, pRoot->right);
    }

};
  • 思路二，迭代，队列。
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(pRoot==NULL) return true;
        if(pRoot->left==NULL && pRoot->right==NULL) return true;
        if(pRoot->left==NULL || pRoot->right==NULL) return false;
        queue<TreeNode*> queueA, queueB;
        queueA.push(pRoot->left);
        queueB.push(pRoot->right);
        while(!queueA.empty() && !queueB.empty()){
            TreeNode* pA = queueA.front();
            TreeNode* pB = queueB.front();
            queueA.pop();
            queueB.pop();
            if(pA==NULL && pB==NULL) continue;
            if(pA==NULL || pB==NULL) return false;
            if(pA->val != pB->val) return false;
            queueA.push(pA->left);
            queueA.push(pA->right);
            queueB.push(pB->right);
            queueB.push(pB->left);
        }
        return queueA.empty() && queueB.empty();
    }
};
  • 思路二，迭代，栈，把上面队列的代码里面所有的queue替换成stack，front()方法换成top()即可，其他不用变。
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(pRoot==NULL) return true;
        stack<TreeNode*> stackA, stackB;
        stackA.push(pRoot->left);
        stackB.push(pRoot->right);
        while(!stackA.empty() && !stackB.empty()){
            TreeNode* pA = stackA.top();
            TreeNode* pB = stackB.top();
            stackA.pop();
            stackB.pop();
            if(pA==NULL && pB==NULL) continue;
            if(pA==NULL || pB==NULL) return false;
            if(pA->val != pB->val) return false;
            stackA.push(pA->left);
            stackA.push(pA->right);
            stackB.push(pB->right);
            stackB.push(pB->left);
        }
        return stackA.empty() && stackB.empty();
    }
};