两种方法:
- 递归法——左子树与右子树比较、右子树与左子树比较(
3ms + 504KB
) - 迭代法——借助两个栈实现(
3ms + 376KB
)
递归
// // Created by jt on 2020/8/22. // using namespace std; class Solution { public: /** * * @param root TreeNode类 * @return bool布尔型 */ bool isSymmetric(TreeNode *root) { // write code here if (!root) return true; return isChildSymmetric(root->left, root->right); } bool isChildSymmetric(TreeNode *left, TreeNode *right) { // 中左右 中右左 if (!left && !right) return true; if (left == nullptr ^ right == nullptr) return false; if (left->val != right->val) return false; return isChildSymmetric(left->left, right->right) && isChildSymmetric(left->right, right->left); } };
迭代
// // Created by jt on 2020/8/22. // #include <stack> using namespace std; class Solution { public: /** * * @param root TreeNode类 * @return bool布尔型 */ bool isSymmetric(TreeNode *root) { // write code here if (!root) return true; if (!root->left && !root->right) return true; if (root->left == nullptr ^ root->right == nullptr) return false; stack<TreeNode *> st1, st2; // 中左右 中右左 st1.push(root->left); st2.push(root->right); while (!st1.empty() && !st2.empty()) { TreeNode *node1 = st1.top(), *node2 = st2.top(); st1.pop(); st2.pop(); if (node1->val != node2->val) return false; if (node1->left == nullptr ^ node2->right == nullptr) return false; if (node1->right == nullptr ^ node2->left == nullptr) return false; if (node1->left) st1.push(node1->left); if (node1->right) st1.push(node1->right); if (node2->right) st2.push(node2->right); if (node2->left) st2.push(node2->left); } if (st1.empty() && st2.empty()) return true; return false; } };