【LeetCode】101. Symmetric Tree

LeetCode-101

Links:https://leetcode.com/problems/symmetric-tree/

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

For example, this binary tree is symmetric:

/ \

2 2

/ \ / \

3 4 4 3

But the following is not:

/ \

2 2

\ \

3 3

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

题目大意：判断是否对称，要求用循环和递归两种方法做。

递归思路：比较左右节点，然后递归比较左左和右右，左右和右左（对称）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* left ,TreeNode* right){
        if(left == NULL && right == NULL) return true;
        if(left == NULL || right == NULL) return false;
        if(left->val!=right->val) return false;
        return isSymmetric(left->left,right->right) && isSymmetric(left->right,right->left);
    }
    
    bool isSymmetric(TreeNode* root) {
        if(root == NULL)return true;
        else return isSymmetric(root->left,root->right);
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

bool isSymmetric(TreeNode* left ,TreeNode* right){

if(left == NULL && right == NULL) return true;

if(left == NULL || right == NULL) return false;

if(left->val!=right->val) return false;

return isSymmetric(left->left,right->right) && isSymmetric(left->right,right->left);

}

bool isSymmetric(TreeNode* root) {

if(root == NULL)return true;

else return isSymmetric(root->left,root->right);

}

};

循环思路：用两个栈存储，反向进行push。对于

/ \

2 2

/ \ / \

3 4 4 3

这样的，两个栈的插入顺序如下：

L：2,3,4.分别是（中，左，右）

R：2,3,4.分别是（中，右，左）

至于比较顺序，不需要管它，因为可以保证是相同的。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root)return true;
        stack<TreeNode*>L;
        stack<TreeNode*>R;
        L.push(root->left);
        R.push(root->right);
        while(!L.empty() && !R.empty())
        {
            TreeNode* l = L.top();
            L.pop();
            TreeNode* r = R.top();
            R.pop();
            if(!l && !r)continue;
            if(!l || !r)return false;
            if(l->val != r->val)return false;
            
            L.push(l->left);
            L.push(l->right);
            R.push(r->right);
            R.push(r->left);
        }
        return true;
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

bool isSymmetric(TreeNode* root) {

if(!root)return true;

stack<TreeNode*>L;

stack<TreeNode*>R;

L.push(root->left);

R.push(root->right);

while(!L.empty() && !R.empty())

{

TreeNode* l = L.top();

L.pop();

TreeNode* r = R.top();

R.pop();

if(!l && !r)continue;

if(!l || !r)return false;

if(l->val != r->val)return false;

L.push(l->left);

L.push(l->right);

R.push(r->right);

R.push(r->left);

}

return true;

}

};

…

【LeetCode】101. Symmetric Tree

Tagged on: LeetCode