101. Symmetric Tree

101. Symmetric Tree (Easy)

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

 

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

 

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• -100 <= Node.val <= 100

 

Follow up:

Companies: Amazon, Yandex, TikTok

Related Topics:
Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution 1.

// OJ: https://leetcode.com/problems/symmetric-tree
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
    bool dfs(TreeNode* A, TreeNode* B) {
        return (!A && !B) || (A && B && A->val == B->val && dfs(A->left, B->right) && dfs(A->right, B->left));
    }
public:
    bool isSymmetric(TreeNode* root) {
        return dfs(root->left, root->right);
    }
};