我的书签
添加书签
移除书签- Symmetric Tree
Symmetric Tree
Given a binary tree, check whether it is a mirror of itself(ie, symmetric around its center) For example, this tree is symmetric: 1. 1 2. / \ 3. 2 2 4. / \ / \ 5. 3 4 4 3
But the following tree is not. 1. 1 2. / \ 3. 2 2 4. \ \ 5. 3 3
题目翻译：
判断一棵树是不是自己的镜像， 根据以上正反两个例子，我想大家都明白这道题的题目要求了，简单明了.
解题思路:
递归:
这道题没什么特别的地方，现在这里简单的分析一下解题思路，从根节点往下，我们要判断三个条件.
1. 左右两个节点的大小是否相同.
2. 左节点的左孩子是否和右节点的右孩子相同.
3. 左节点的右孩子是否和右节点的左孩子相同.
循环:
这道题的难点在于循环解法， 如果是循环解法，我们必须要用到额外的存储空间用于回溯，关键是对于这道题目， 我们要用多少？要怎么用？要用什么样的存储空间？
递归求解，如果以上三个条件对于每一层都满足，我们就可以认为这棵树是镜像树.
时间复杂度:
递归:本质其实就是DFS,时间复杂度为O(n),空间复杂度O(1)
递归:时间复杂度O(n),空间复杂度O(n)
递归代码如下:
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)
14. return true;
15. return Helper(root->left,root->right);
16. }
17. 18. bool Helper(TreeNode left, TreeNode right)
19. {
20. if(left == NULL&&right == NULL)
21. return true;
22. else if(left == NULL||right == NULL)
23. return false;
24. bool cond1 = left->val == right->val;
25. bool cond2 = Helper(left->left,right->right);
26. bool cond3 = Helper(left->right, right->left);
27. return cond1&&cond2&&cond3;
28. }
29. 30. };
循环解法:
我们主要想介绍一下这道题的循环解法，对于循环，我们要满足对于每一层进行check，代替了递归，一般树的循环遍历，我们都是用FIFO的queue来作为临时空间存储变量的，所以这道题我们也选取了queue，但是我们用两个queue，因为我们要对于左右同时进行检查，很显然一个queue是不够的，具体实现细节，咱们还是看代码吧，，我相信代码更能解释方法.
循环代码如下:
1. 2. /
3. * Definition for binary tree
4. * struct TreeNode {
5. * int val;
6. * TreeNode left;
7. * TreeNode right;
8. * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9. * };
10. /
11. class Solution {
12. public:
13. bool isSymmetric(TreeNode root) {
14. if(root == NULL)
15. return true;
16. TreeNode n1 = root->left;
17. TreeNode n2 = root->right;
18. if(!n1&&!n2)
19. return true;
20. if((!n1&&n2)||(n1&&!n2))
21. return false;
22. queue
