100/101-对称二叉树

LeetCode 100. Same Tree

LeetCode-100

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

method

先看当前节点，再分别看左右子树

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;
    else if (!p && q) return false;
    else if (p && !q) return false;
    else if (p->val != q->val) return false;
    bool leftSide = isSameTree(p->left, q->left);
    bool rightSide = isSameTree(p->right, q->right);
    return leftSide && rightSide;
}

---

LeetCode 101. Symmetric Tree

LeetCode-101

Given the root of a binary tree, check whether it is a mirror of itself.

Example:

method:递归

分别比较外侧节点和内侧节点

• 外侧：左子树的左节点，右子树的右节点
• 内侧：左子树的右节点，右子树的左节点

递归参数：在不引起争议的情况下，统称为左节点和右节点

结束条件：

1. 左节点空，右节点也空，返回true
2. 左节点非空，右节点空，返回false
3. 左节点空，右节点非空，返回false
4. 左右节点都不空，但是不相等，返回false

单层遍历逻辑：分别遍历内侧节点和外侧节点

bool compare(TreeNode* left, TreeNode* right) {
    if (left == nullptr && right == nullptr) return true;
    else if (left != nullptr && right == nullptr) return false;
    else if (left == nullptr && right != nullptr) return false;
    else if (left->val != right->val) return false;
    // 剩下的就是节点非空且值相同的情况
    bool outSide = compare(left->left, right->right);
    bool inSide = compare(left->right, right->left);
    return outSide && inSide;
}
bool isSymmetric(TreeNode* root) {
    if (root == nullptr) return true;
    return compare(root->left, root->right);
}