Home Symmetric Tree
Post
Cancel

LeetCode #101: Symmetric Tree (C/C++).

easy

source: https://leetcode.com/problems/symmetric-tree
C/C++ Solution to LeetCode problem 101. Symmetric Tree.

Problem


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

Examples


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: Could you solve it both recursively and iteratively?

Solution


  1. We have two parts for every node (left and right), we need to check if left == right. Will use a BFS (Breadth First Search) algorithm. - Insert the root nodes to the queue using pair<TreeNode*, TreeNode*>. - While the queue has nodes:
    • If one node exists, but the other no, return false.
    • If both nodes exist but their values are different, return false.

    • Insert to the queue two pairs left and right and right and left
    • Pop the first element (pair of nodes) from the queue.
      • Return true.
  2. A Depth First Search solution.

Solution 1:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * 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:
  bool isSymmetric(TreeNode* root) {
    queue<pair<TreeNode *, TreeNode *>> bfs;

    bfs.push({root->left, root->right});
    TreeNode *a;
    TreeNode *b;
    
    while (!bfs.empty()) {
      a = bfs.front().first;
      b = bfs.front().second;
      if (!a != !b)
        return false;
      if (a && b) {
        if (a->val != b->val)
          return false;

        bfs.push({a->left, b->right});
        bfs.push({a->right, b->left});
      }
      bfs.pop();
    }

    return true;
  }
};

Solution 2:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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 {
private:
  bool exploreNode(TreeNode* nodeL, TreeNode* nodeR) {
    if (!nodeL != !nodeR)
      return false;
    if (!nodeL && !nodeR)
      return true;

    bool a = exploreNode(nodeL->left, nodeR->right);
    bool b = exploreNode(nodeL->right, nodeR->left);

    if (!a || !b) 
      return false;

    return nodeL->val == nodeR->val;
  }

public:
  bool isSymmetric(TreeNode* root) {
    return exploreNode(root->left, root->right);
  }
};
This post is licensed under CC BY 4.0 by the author.

Same Tree

Balanced Binary Tree