IT虾米网

对称的二叉树算法详解

itxm 2020年11月13日 编程语言 166 0

题目描述

请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。
 
解:
这道题首先想到的就是按前中后序的一种方法,塞入栈中进行压入弹出的方法
还有一种递归对比左右两树的方法
 
 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 };

 

 
发布评论

分享到:

IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

STL——萃取机制(Traits)详解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。