二叉树 Leetcode 101 对称二叉树
Leetcode 101
要点:1.比较的是左右子树是否相同,不是节点的左右孩子;
2.左子树左右中遍历,右子树右左中遍历;
3.灵活递归。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 1.确定递归参数和返回值
bool compare(TreeNode* left, TreeNode* right){
// 2.确定终止条件
if(left == nullptr && right != nullptr) return false;
else if(left != nullptr && right == nullptr) return false;
else if(left == nullptr && right == nullptr) return true;
else if(left->val != right->val) return false;
// 3.单次递归逻辑
bool out = compare(left->left, right->right);
bool in = compare(left->right, right->left);
bool isSame = out && in;
return isSame;
}
bool isSymmetric(TreeNode* root) {
if(root->left == nullptr && root->right != nullptr){
return false;
}else if(root->left != nullptr && root->right == nullptr){
return false;
}
return compare(root->left, root->right);
}
};