首页 > 代码库 > leetcode - Symmetric Tree

leetcode - Symmetric Tree

题目: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:

    1   /   2   2 / \ / 3  4 4  3

 

But the following is not:

    1   /   2   2   \      3    3

 

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

 

个人思路:

1、注意到根节点的左右子树是对称的,且对称方向是左右对称,那么选取根节点的任意一颗子树,这里我选取右子树

2、将右子树中的所有父节点的左右子节点互换,如果原来的树是一颗镜像树,那么右子树经过这么处理后便与左子树相同,因此,只需要将处理之后的右子树与原来的左子树对比是否相同,若相同,则原树是镜像树,否则不是镜像树

 

代码:

 1 #include <stddef.h> 2 #include <iostream> 3  4 using namespace std; 5  6 struct TreeNode 7 { 8     int val; 9     TreeNode *left;10     TreeNode *right;11     TreeNode(int x) : val(x), left(NULL), right(NULL) {}12 };13 14 class Solution15 {16 public:17     bool isSymmetric(TreeNode *root)18     {19         if (root == NULL || (root->left == NULL && root->right == NULL))20         {21             return true;22         }23         if ((root->left == NULL && root->right != NULL) || (root->right == NULL && root->left != NULL))24         {25             return false;26         }27         //根节点及其左右子节点均不为空28         swapLeftRight(root->right);29 30         return isSameTree(root->left, root->right);31     }32 private:33     void swapLeftRight(TreeNode *root)34     {35         if (root == NULL)36         {37             return;38         }39 40         TreeNode *tmp = root->right;41         root->right = root->left;42         root->left = tmp;43 44         swapLeftRight(root->left);45         swapLeftRight(root->right);46     }47     bool isSameTree(TreeNode *first, TreeNode *second)48     {49         if (first == NULL && second == NULL)50         {51             return true;52         }53         if (first != NULL && second != NULL)54         {55             return first->val == second->val && isSameTree(first->left, second->left) && isSameTree(first->right, second->right);56         }57 58         return false;59     }60 };61 62 int main()63 {64     Solution s;65     TreeNode *root = new TreeNode(1);66     root->left = new TreeNode(2);67     root->right = new TreeNode(2);68     //root->left->left = new TreeNode(3);69     root->left->right = new TreeNode(3);70     //root->right->left = new TreeNode(4);71     root->right->right = new TreeNode(3);72 73     cout << s.isSymmetric(root) << endl;74 75     system("pause");76 77     return 0;78 }
View Code

 

上网搜了一些帖子,发现我的方法过于麻烦,可以处理地更简单些,链接:http://www.cnblogs.com/remlostime/archive/2012/11/15/2772230.html,这是递归的算法,思路是从根节点的左右子节点开始判断,判断左右子节点值,再判断左节点的左子树与右节点的右子树是否相同,以及左节点的右子树与右节点的左子树是否相同

 

代码:

  1 #include <stddef.h>  2 #include <iostream>  3   4 using namespace std;  5   6 struct TreeNode  7 {  8     int val;  9     TreeNode *left; 10     TreeNode *right; 11     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 12 }; 13  14 class Solution 15 { 16 public: 17     bool isSymmetric(TreeNode *root) 18     { 19         /* 20         if (root == NULL || (root->left == NULL && root->right == NULL)) 21         { 22             return true; 23         } 24         if ((root->left == NULL && root->right != NULL) || (root->right == NULL && root->left != NULL)) 25         { 26             return false; 27         } 28         //根节点及其左右子节点均不为空 29         swapLeftRight(root->right); 30  31         return isSameTree(root->left, root->right); 32         */ 33  34         if (root == NULL) 35         { 36             return true; 37         } 38  39         return isSame(root->left, root->right); 40     } 41 private: 42     bool isSame(TreeNode *left, TreeNode *right) 43     { 44         if (left == NULL && right == NULL) 45         { 46             return true; 47         } 48         if (left == NULL || right == NULL) 49         { 50             return false; 51         } 52  53         return left->val == right->val && isSame(left->left, right->right) && isSame(left->right, right->left); 54     } 55     void swapLeftRight(TreeNode *root) 56     { 57         if (root == NULL) 58         { 59             return; 60         } 61  62         TreeNode *tmp = root->right; 63         root->right = root->left; 64         root->left = tmp; 65  66         swapLeftRight(root->left); 67         swapLeftRight(root->right); 68     } 69     bool isSameTree(TreeNode *first, TreeNode *second) 70     { 71         if (first == NULL && second == NULL) 72         { 73             return true; 74         } 75         if (first != NULL && second != NULL) 76         { 77             return first->val == second->val && isSameTree(first->left, second->left) && isSameTree(first->right, second->right); 78         } 79  80         return false; 81     } 82 }; 83  84 int main() 85 { 86     Solution s; 87     TreeNode *root = new TreeNode(1); 88     root->left = new TreeNode(2); 89     root->right = new TreeNode(2); 90     //root->left->left = new TreeNode(3); 91     root->left->right = new TreeNode(3); 92     //root->right->left = new TreeNode(4); 93     root->right->right = new TreeNode(3); 94  95     cout << s.isSymmetric(root) << endl; 96  97     system("pause"); 98  99     return 0;100 }
View Code

 

非递归的算法,链接:http://blog.csdn.net/sunbaigui/article/details/8981333

 

思路:

1、类似层次遍历的方法,根节点的左右子树分别进行各自的层次遍历,且相同层次上的遍历顺序相反

2、左子树从左往右,右子树从右往左,如果原树是镜像树,那么遍历出来的节点以及节点值应该相同,否则不是镜像树

 

代码:

  1 #include <stddef.h>  2 #include <iostream>  3 #include <queue>  4   5 using namespace std;  6   7 struct TreeNode  8 {  9     int val; 10     TreeNode *left; 11     TreeNode *right; 12     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 13 }; 14  15 class Solution 16 { 17 public: 18     bool isSymmetric(TreeNode *root) 19     { 20         /* 21         if (root == NULL || (root->left == NULL && root->right == NULL)) 22         { 23             return true; 24         } 25         if ((root->left == NULL && root->right != NULL) || (root->right == NULL && root->left != NULL)) 26         { 27             return false; 28         } 29         //根节点及其左右子节点均不为空 30         swapLeftRight(root->right); 31  32         return isSameTree(root->left, root->right); 33         */ 34         /* 35         if (root == NULL) 36         { 37             return true; 38         } 39  40         return isSame(root->left, root->right); 41         */ 42  43         if (root == NULL) 44         { 45             return true; 46         } 47  48         queue<TreeNode *> left, right; 49         left.push(root->left); 50         right.push(root->right); 51  52         while (!left.empty() && !right.empty()) 53         { 54             TreeNode *leftNode = left.front(); 55             TreeNode *rightNode = right.front(); 56             left.pop(); 57             right.pop(); 58  59             if (leftNode == NULL && rightNode == NULL) 60             { 61                 continue; 62             } 63             if (leftNode == NULL || rightNode == NULL) 64             { 65                 return false; 66             } 67             if (leftNode->val != rightNode->val) 68             { 69                 return false; 70             } 71  72             left.push(leftNode->left); 73             left.push(leftNode->right); 74             right.push(rightNode->right); 75             right.push(rightNode->left); 76         } 77  78         return true; 79  80     } 81 private: 82     bool isSame(TreeNode *left, TreeNode *right) 83     { 84         if (left == NULL && right == NULL) 85         { 86             return true; 87         } 88         if (left == NULL || right == NULL) 89         { 90             return false; 91         } 92  93         return left->val == right->val && isSame(left->left, right->right) && isSame(left->right, right->left); 94     } 95     void swapLeftRight(TreeNode *root) 96     { 97         if (root == NULL) 98         { 99             return;100         }101 102         TreeNode *tmp = root->right;103         root->right = root->left;104         root->left = tmp;105 106         swapLeftRight(root->left);107         swapLeftRight(root->right);108     }109     bool isSameTree(TreeNode *first, TreeNode *second)110     {111         if (first == NULL && second == NULL)112         {113             return true;114         }115         if (first != NULL && second != NULL)116         {117             return first->val == second->val && isSameTree(first->left, second->left) && isSameTree(first->right, second->right);118         }119 120         return false;121     }122 };123 124 int main()125 {126     Solution s;127     TreeNode *root = new TreeNode(1);128     root->left = new TreeNode(2);129     root->right = new TreeNode(2);130     //root->left->left = new TreeNode(3);131     root->left->right = new TreeNode(3);132     //root->right->left = new TreeNode(4);133     root->right->right = new TreeNode(3);134 135     cout << s.isSymmetric(root) << endl;136 137     system("pause");138 139     return 0;140 }
View Code