LeetCode 101 Symmetric Tree（对称树）（*）

对称树）（*）"/>

LeetCode 101 Symmetric Tree（对称树）（*）

翻译

给定一个二叉树，检查它是否是它本身的镜像（也就是说，中心对称）。例如，这个二叉树是对称的：1/ \
  2   2/ \ / \
3  4 4  3但是下面这个却不是：1/ \
  2   2\   \
   3    3批注：
如果你能同时用递归和迭代来解决这个问题，这会是加分项。

原文

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  3But the following is not:1/ \2   2\   \3    3Note:
Bonus points if you could solve it both recursively and iteratively.

分析

其实吧，这道题和下面这道题的思路非常的类似，都是从上向下不断的遍历，只不过是比较的对象不一样而已。

LeetCode 110 Balanced Binary Tree（平衡二叉树）（*）

一开始我写了下面这段代码，不过后来发现错了，镜像不是这么回事……下面的代码是每个节点的左右子节点对称，而镜像是对于整个树而言的一种对称。所以继续改改改……

bool isSymmetric(TreeNode* root) {if (!root || (!root->left && !root->right)) return true;else if (!root->left || !root->right) return false;if (root->left->val != root->right->val)return false;else if (!isSymmetric(root->left) || !isSymmetric(root->right)) return false;return true;
}

经过无数次的修改，最终成了如下版本：

bool  isSymmetricIter(TreeNode* r1, TreeNode* r2) {if (!r1 && !r2)  return true;else if (!r1 || !r2) return false;if ((!r1->left && !r2->right && !r1->right && !r2->left)) return true;if ((r1->left && r2->right)) {if (r1->left->val != r2->right->val)return false;}else if (!r1->left && !r2->right) {}else return false;if ((r1->right && r2->left)) {if (r1->right->val != r2->left->val)return false;}else if (!r1->right && !r2->left) {}else return false;if (!isSymmetricIter(r1->left, r2->right) || !isSymmetricIter(r1->right, r2->left)) return false;return true;
}bool isSymmetric(TreeNode* root) {if (!root) return true;else if (!root->left && !root->right) return true;else if (!root->left || !root->right) return false;else if (root->left->val != root->right->val) return false;return isSymmetricIter(root->left, root->right);return isSymmetricIter(root->left, root->right);
}

后来继续修改修改，让它更简洁一些。

bool  isSymmetricIter(TreeNode* r1, TreeNode* r2) {if (!r1 && !r2)  return true;else if (!r1 || !r2) return false;if (!r1->left && !r2->right && !r1->right && !r2->left) return true;if ((r1->left && r2->right)) {if (r1->left->val != r2->right->val)return false;}else if (!(!r1->left && !r2->right)) return false;if ((r1->right && r2->left)) {if (r1->right->val != r2->left->val)return false;}else if (!(!r1->right && !r2->left)) return false;if (!isSymmetricIter(r1->left, r2->right) || !isSymmetricIter(r1->right, r2->left)) return false;return true;
}bool isSymmetric(TreeNode* root) {if (!root) return true;return isSymmetricIter(root, root);
}