首页 > 代码库 > Symmetric Tree <LeetCode>

Symmetric Tree <LeetCode>

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

For example, this binary tree is symmetric:

 

    1   /   2   2 / \ / 3  4 4  3

 

But the following is not:

    1   /   2   2   \      3    3


思路:首先把想到用递归分别遍历左右子树,不同的时,遍历左子树时,先遍历根节点,然后是左孩子,最后右孩子;遍历右子树时,县遍历根节点,然后是右孩子,最后是左孩子,每遍历到一个节点进行比较,是否相同,代码如下://没有优化

 1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     bool isSymmetric(TreeNode *root) {13         if(root==NULL)  return true;14         TreeNode *rootl;15         TreeNode *rootr;16         rootl=root->left;17         rootr=root->right;18         return isSame(rootl,rootr);19     }20     21     bool isSame(TreeNode *rootl,TreeNode *rootr)22     {23         if(rootl==NULL||rootr==NULL)24         {25             if(rootl!=NULL||rootr!=NULL)26             {27                 return false;28             }29             else return true;30         }31         32         if(rootl->val!=rootr->val)  return false;33         else34         {35             if(isSame(rootl->left,rootr->right))36             {37                 if(isSame(rootl->right,rootr->left))38                 {39                     return true;40                 }41                 else return false;42             }43             else return false;44         }45         46     }47 };

 

Symmetric Tree <LeetCode>