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.

解题思路：

递归：左指针和右指针，对称递归，即“左的左”和“右的右”对应，“左的右”和“右的左”对应。

非递归：中序遍历左子树，将结果保存起来，中序遍历右子树将结果保存起来；顺序比较每个元素是否相等。

代码：

 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 judge(TreeNode *p_left, TreeNode *p_right) {
13         if (p_left == NULL && p_right == NULL) {
14             return true;
15         } else if ((p_left != NULL && p_right == NULL) || (p_left == NULL && p_right != NULL)) {
16             return false; 
17         }
18         
19         if (p_left->val != p_right->val) return false;
20         
21         if ((p_left->left != p_right->right && (p_left->left == NULL || p_right->right == NULL)) ||
22             (p_left->right != p_right->left && (p_left->right == NULL || p_right->left == NULL))) {
23                 return false;
24         }
25 
26         return judge(p_left->left, p_right->right) && judge(p_left->right, p_right->left); 
27         
28     }
29     bool isSymmetric(TreeNode *root) {
30         if (root == NULL || (root->left == NULL && root->right == NULL)) {
31             return true;
32         } else if (root->left == NULL || root->right == NULL) {
33             return false;
34         } 
35         if (root->left->val == root->right->val) {
36             return judge(root->left, root->right);
37         }
38         return false;
39     }
40 };

LeetCode OJ 题目： 解题思路： 代码：

解题思路：

代码：

相关推荐

LeetCode OJ 题目：解题思路：代码：