首页 > 代码库 > 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 }
上网搜了一些帖子,发现我的方法过于麻烦,可以处理地更简单些,链接: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 }
非递归的算法,链接: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 }