[Leetcode] 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:

But the following is not:

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

confused what"{1,#,2,3}"means? >read more on how binary tree is serialized on OJ.

OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}".

题意：对称指的是二叉树的结构上的对称。不是说某一层以上都是对称的，该层只有两个元素，分别对应上一层对称元素的两右孩子，这也是对称。这种情况的结构上不对称。如题中的反例。

方法一：维护两个队列，层次遍历，一个从左到右，一个从右到左，比较队首借点。思路上有点像判断两二叉树是否相同那题

/**

 * Definition for binary tree

 * 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==nullptr)

            return true;

        queue<TreeNode *> Q1;

        queue<TreeNode *> Q2;

        Q1.push(root->left);

        Q2.push(root->right);

        while( !Q1.empty())

        {

            TreeNode *node1=Q1.front();

            TreeNode *node2=Q2.front();

            Q1.pop();

            Q2.pop();

            if(node1==nullptr&&node2==nullptr)

                continue;

            if(node1==nullptr||node2==nullptr)

                return false;

            if(node1->val !=node2->val)

                return false;

            Q1.push(node1->left);

            Q1.push(node1->right);

            Q2.push(node2->right);

            Q2.push(node2->left);

        }

        return true;

    }

};

/*  //主体的另一种写法

while (!q1.empty() && !q2.empty())

{
TreeNode *node1 = q1.front();
　　TreeNode *node2 = q2.front();
　　q1.pop();
　　q2.pop();
　　if((node1 && !node2) || (!node1 && node2)) return false;
　　if (node1)

　　{
　　　　if (node1->val != node2->val) return false;
　　　　q1.push(node1->left);
　　　　q1.push(node1->right);
　　　　q2.push(node2->right);
　　　　q2.push(node2->left);
　　}

}

方法二：使用栈。特别值得注意的是：入栈的顺序，先左左，后右右，交替入栈，这样，出栈时才能保证同时从一层的两头向中间遍历。循环中，注意的条件：左右同时为0时，这种情况重新遍历即可；有一者为0，则说明不对称，返回false；对应的值不相等，也是返回false；到叶节点以后也是重新遍历未访问的结点即可。

 /**

  * Definition for binary tree

  * 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==NULL||(root->left==NULL&&root->right==NULL))

             return true;

         stack<TreeNode *> stk;

         stk.push(root->left);

         stk.push(root->right);

         while( !stk.empty())

         {

             TreeNode *rNode=stk.top();

             stk.pop();

             TreeNode *lNode=stk.top();

             stk.pop();

             if(rNode==NULL&&lNode=NULL)

                 continue;

             if(rNode==NULL||lNode==NULL)

                 return false;

             if(rNode->val !=lNode->val)

                 return false;

             //判断是否到叶节点，若是返回遍历其他

             if(lNode->left==NULL&&lNode->right==NULL

              &&rNode->left==NULL&&rNode->right==NULL)

                 continue;

             else

             {   //注意顺序，先左左后右右，交替入栈

                 stk.push(lNode->left);

                 stk.push(rNode->right);

                 stk.push(lNode->right);

                 stk.push(rNode->left);

             }

         }

         return true;

     }

 };

方法三：递归

 /**

  * Definition for binary tree

  * 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==NULL)

             return true;

         return subTreeSym(root->left,root->right);

     }

     bool subTreeSym(TreeNode *lNode,TreeNode *rNode)

     {

         if(lNode==NULL&&rNode==NULL)

             return true;

         if(lNode==NULL||rNode==NULL)    //和下面的那个不能颠倒顺序

             return false;

         if(lNode->val !=rNode->val)

             return false;

         return subTreeSym(lNode->left,rNode->right)&&subTreeSym(lNode->right,rNode->left);

     }

 };

巴特西

[Leetcode] Symmetric tree 对称二叉树

最新文章

热门文章