101. 对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

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

  bool isSymmetric(TreeNode* root) {
    // basically dual pointers on a tree...?
    return check(root->left, root->right);
  }
};

这题的 dispatch 的思路特别有意思，你会发现这个 check() 接受的是两个参数而不是我们平常在遍历的时候设计的一个，因为我们就是要每次同时检测两侧的节点。大概可以理解为「树上双指针」？

二刷

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

其实 Dispatch() 里头那最后三行可以写一块去的，也就是 return L->val == R->val && Dispatch(L->left, R->right) && Dispatch(L->right, R->left);

三刷

class Solution {
  bool Check(TreeNode *L, TreeNode *R) {
    if (!L && !R)
      return true;
    // else
    if (!L || !R)
      return false;

    if (L->val != R->val)
      return false;
    // else
    bool Outside = Check(L->left, R->right);
    bool Inside = Check(L->right, R->left);
    return Outside && Inside;
  }
public:
  bool isSymmetric(TreeNode* root) {
    return Check(root->left, root->right);
  }
};

FP还在救我。把所有else显式地写出来确实是好的。