对称的二叉树

题目描述

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

解:

这道题首先想到的就是按前中后序的一种方法，塞入栈中进行压入弹出的方法

还有一种递归对比左右两树的方法

 bool isSymmetricalDFS(TreeNode pRoot)
    {
        if(pRoot == null) return true;
        Stack<TreeNode> s = new Stack<>();
        s.push(pRoot.left);
        s.push(pRoot.right);
        while(!s.empty()) {
            TreeNode right = s.pop();//成对取出
            TreeNode left = s.pop();
            if(left == null && right == null) continue;
            if(left == null || right == null) return false;
            if(left.val != right.val) return false;
            //成对插入
            s.push(left.left);
            s.push(right.right);
            s.push(left.right);
            s.push(right.left);
        }
        return true;
    }

//改为递归的思路如下
/*
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==nullptr)
            return true;
        stack<TreeNode*> tmp;
        tmp.push(pRoot->left);
        tmp.push(pRoot->right);
        return isSymmetrical(tmp);
    }

    bool isSymmetrical(stack<TreeNode*>&std_stack)
    {
            TreeNode *left= std_stack.top();//成对取出
        std_stack.pop();
            TreeNode *right= std_stack.top();
        std_stack.pop();
            if(left==nullptr &&right==nullptr)
                return true;
            else if(left==nullptr ||right==nullptr)
                return false;
            else if(left->val!=right->val)
                return false;
            //两值相等，则塞入堆栈
        std_stack.push(left->left);
        std_stack.push(right->right);
        std_stack.push(left->right);
        std_stack.push(right->left);
        //每次入栈都是两队，递归的话就要调用两次
        return isSymmetrical(std_stack)&&isSymmetrical(std_stack);
    }

};

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };
10 */
11 class Solution {
12 public:
13     bool isSymmetrical(TreeNode* pRoot)
14     {
15         return pRoot==nullptr || isSymmetrical(pRoot->left,pRoot->right);
16     }
17 
18     bool isSymmetrical(TreeNode* pRoot1,TreeNode* pRoot2)
19     {
20         if(pRoot1==NULL&&pRoot2==NULL)
21             return true;
22         if(pRoot1==NULL || pRoot2==NULL)           
23             return false;
24         if(pRoot1->val!=pRoot2->val)
25             return false;
26         return isSymmetrical(pRoot1->left,pRoot2->right) && isSymmetrical(pRoot1->right,pRoot2->left);
27          
28     }
29  
30 };

原文链接: https://www.cnblogs.com/wangshaowei/p/12260470.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/391351

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

对称的二叉树

题目描述

相关推荐