剑指offer 判断树是不是对称的

时间：2022-11-15 14:50:01

html, body {
font-size: 15px;
}

body {
font-family: Helvetica, "Hiragino Sans GB", 微软雅黑, "Microsoft YaHei UI", SimSun, SimHei, arial, sans-serif;
line-height: 1.6;
color: ;
background-color: ;
margin: 0;
padding: 16px 20px;
}

h1, h2, h3, h4, h5, h6 {
margin: 20px 0 10px;
margin: 1.33rem 0 0.667rem;
padding: 0;
font-weight: bold;
}

h1 {
font-size: 21px;
font-size: 1.4rem;
}

h2 {
font-size: 20px;
font-size: 1.33rem;
}

h3 {
font-size: 18px;
font-size: 1.2rem;
}

h4 {
font-size: 17px;
font-size: 1.13rem;
}

h5 {
font-size: 15px;
font-size: 1rem;
}

h6 {
font-size: 15px;
font-size: 1rem;
color: #777777;
margin: 1rem 0;
}

div, p, ul, ol, dl, li {
margin: 0;
}
blockquote, table, pre, code{
margin: 8px 0;
}

ul, ol {
padding-left: 32px;
padding-left: 2.13rem;
}

blockquote {
border-left: 4px solid #dddddd;
padding: 0 12px;
padding: 0 0.8rem;
}

blockquote > :first-child {
margin-top: 0;
}

blockquote > :last-child {
margin-bottom: 0;
}

img {
border: 0;
max-width: 100%;
height: auto !important;
margin: 2px 0;
}

table {
border-collapse: collapse;
border: 1px solid #bbbbbb;
}

td {
padding:4px 8px;
border-collapse: collapse;
border: 1px solid #bbbbbb;
}

@media screen and (max-width: 660px) {
body {
padding: 20px 18px;
padding: 1.33rem 1.2rem;
}
}

@media only screen and (-webkit-max-device-width: 1024px), only screen and (-o-max-device-width: 1024px), only screen and (max-device-width: 1024px), only screen and (-webkit-min-device-pixel-ratio: 3), only screen and (-o-min-device-pixel-ratio: 3), only screen and (min-device-pixel-ratio: 3) {
html, body {
font-size: 17px;
}

body {
line-height: 1.7;
padding: 0.75rem 0.9375rem;
color: #353c47;
}

h1 {
font-size: 2.125rem;
}

h2 {
font-size: 1.875rem;
}

h3 {
font-size: 1.625rem;
}

h4 {
font-size: 1.375rem;
}

h5 {
font-size: 1.125rem;
}

h6 {
color: inherit;
}

ul, ol {
padding-left: 2.5rem;
}

blockquote {
padding: 0 0.9375rem;
}
}

剑指offer 判断树是不是对称的

递归是很常见的实现方式，最简便。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
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) return true;
        return compRoot(pRoot -> left, pRoot -> right);
    }
    //递归方法
    bool compRoot(TreeNode* lroot, TreeNode* rroot){
        if(!lroot) return (NULL == rroot);
        if(NULL == rroot) return false;
        if(lroot -> val != rroot -> val) return false;
        return (compRoot(lroot -> left, rroot -> right) && compRoot(lroot -> right, rroot -> left));
    }
 
 
};
迭代版本
使用栈stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
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 *> s;
        s.push(pRoot->left);
        s.push(pRoot->right);
        while(!s.empty()){
            auto p=s.top();s.pop();
            auto q=s.top();s.pop();
            if(!p && !q)continue; //p,q都是NULL，则继续
            if(!p || !q)return false; // p,q中有一个是null，另一个不是,false
            if(p->val !=q->val)return false; // p,q都不是null，但是值不相等，false
             
            s.push(p->left);
            s.push(q->right);
             
            s.push(p->right);
            s.push(q->left);               
        }       
        return true;
    }
};

相关文章