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.
递归的解法：
新建一个递归调用自身的函数，输入是待比较的左结点和右结点，输出是对称判定结果：true or false；
1 class Solution { 2 public: 3 bool isSymmetric(TreeNode *root) { 4 if (!root) 5 return true; 6 7 return isSame(root->left, root->right); 8 9 }10 11 bool isSame(TreeNode *node_l, TreeNode *node_r){12 if (!node_l && !node_r)13 return true;14 15 if (!node_l || !node_r)16 return false;17 18 if (node_l->val != node_r->val){19 return false;20 }21 22 return isSame(node_l->left, node_r->right) && \23 isSame(node_l->right, node_r->left);24 }25 26 };
迭代的解法：
新建两个栈用于存放待比较的左子树结点和右子树结点。每次迭代拿出两个栈中同位置元素进行比较，结束后删除此比较过的元素，并将其左右儿子压栈待比较。（还有只用一个栈的方法，并没有节省空间，略）
1 class Solution { 2 public: 3 bool isSymmetric(TreeNode *root) { 4 if (!root) 5 return true; 6 7 stack leftNodeStack; 8 stack rightNodeStack; 9 leftNodeStack.push(root->left);10 rightNodeStack.push(root->right);11 TreeNode *leftNode;12 TreeNode *rightNode;13 14 while (!leftNodeStack.empty()) {15 leftNode = leftNodeStack.top();16 rightNode = rightNodeStack.top();17 leftNodeStack.pop();18 rightNodeStack.pop();19 20 if (!leftNode && !rightNode) {21 continue;22 }23 24 if ((!leftNode && rightNode) || \25 (leftNode && !rightNode)) {26 return false;27 }28 29 if (leftNode->val != rightNode->val) { 30 return false;31 }32 33 leftNodeStack.push(leftNode->left);34 leftNodeStack.push(leftNode->right);35 rightNodeStack.push(rightNode->right); // Notice36 rightNodeStack.push(rightNode->left);37 }38 return true;39 }40 };
