101. Symmetric Tree - cocoder39/coco39_LC GitHub Wiki

101. Symmetric Tree

there are two cases: 1 check a single root 2 compare two node. main function handle first case and helper() handle second case

top down + dfs, time complexity is O(n) and space complexity is O(h), typical dfs call stack.

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
      if(! root) {
          return true;
      }
      return helper(root->left, root->right);
    }
private: 
    bool helper(TreeNode* p, TreeNode* q) {
        if(! p && ! q) {
            return true;
        }
        if(! p || ! q || p->val != q->val) {
            return false;
        }
        return helper(p->left, q->right) && helper(p->right, q->left);
    }
};