Jocodoma

Joco's Tech Blog

0%

[LeetCode] 0101 Symmetric Tree

Posted on In , , Disqus:
Symbols count in article: 2.4k Reading time ≈ 2 mins.

Symmetric Tree

LeetCode - 0101 Symmetric Tree
https://leetcode.com/problems/symmetric-tree/

Problem Description

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree [1, 2, 2, 3, 4, 4, 3] is symmetric:

1
2
3
4
5
    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1, 2, 2, null, 3, null, 3] is not:

1
2
3
4
5
  1
 / \
2   2
 \   \
 3    3

Solutions

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  bool isSymmetric(TreeNode* root) {
    return isMirror(root, root);
  }

  bool isMirror(TreeNode* leftSubTree, TreeNode* rightSubTree){
    if(!leftSubTree && !rightSubTree) return true;
    if(!leftSubTree || !rightSubTree) return false;
    if(leftSubTree->val != rightSubTree->val) return false;
    return isMirror(leftSubTree->left, rightSubTree->right) && isMirror(leftSubTree->right, rightSubTree->left);
  }
};

  • Time complexity: O(n)
    Because we traverse the entire input tree once, the total run time is O(n), where n is the total number of nodes in the tree.

  • Space complexity: O(n)
    The number of recursive calls is bound by the height of the tree. In the worst case, the tree is linear(unbalanced) and the height is in O(n). Therefore, space complexity due to recursive calls on the stack is O(n) in the worst case.

Iteration

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  bool isSymmetric(TreeNode* root) {
    std::stack<TreeNode*> nodeStack;
    nodeStack.push(root);
    nodeStack.push(root);

    while(!nodeStack.empty()){
      TreeNode *leftNode = nodeStack.top(); nodeStack.pop();
      TreeNode *rightNode = nodeStack.top(); nodeStack.pop();

      if(!leftNode && !rightNode) continue;
      if(!leftNode || !rightNode) return false;
      if(leftNode->val != rightNode->val) return false;

      nodeStack.push(leftNode->left);
      nodeStack.push(rightNode->right);
      nodeStack.push(leftNode->right);
      nodeStack.push(rightNode->left);
    }
    return true;
  }
};

  • Time complexity: O(n)
    Because we traverse the entire input tree once, the total run time is O(n), where n is the total number of nodes in the tree.

  • Space complexity: O(n)
    There is additional space required for the search stack. In the worst case, we have to insert O(n) nodes in the stack. Therefore, space complexity is O(n).