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.
此题要求判断一个二叉树是否是左右对称的，且期望能够同时尝试一下迭代的方法和递归的方法。递归的方法相对来说简单一些，也更易读懂。迭代的方法需要利用栈来实现。
递归方法：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isSymmetric(TreeNode* root) { if (!root) return true; return childSymmetric(root->left, root->right); } bool childSymmetric(TreeNode* l, TreeNode* r) { if (!l && !r) return true; if (!l || !r) return false; return l->val == r->val && childSymmetric(l->left, r->right) && childSymmetric(l->right, r->left); } };
迭代方法：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isSymmetric(TreeNode* root) { if (!root) return true; TreeNode *l, *r; stack<TreeNode*> s; if (root->left) { if (!root->right) return false; s.push(root->left); s.push(root->right); } else if (root->right) return false; while(!s.empty()) { l = s.top();s.pop(); r = s.top();s.pop(); if (l->val != r->val) return false; if (l->left) { if (!r->right) return false; s.push(l->left); s.push(r->right); } else if (r->right) return false; if (l->right) { if (!r->left) return false; s.push(l->right); s.push(r->left); } else if (r->left) return false; } return true; } };
原文：http://www.cnblogs.com/jdneo/p/4786926.html