LeetCode 101. Symmetric Tree [Easy] [C++] 解題筆記

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   2
 / \    / \
3  4 4  3

 

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

    1
    / \
  2   2
   \    \
   3    3

想法:

    這題使用 recursive 的方式實作的話非常簡單，從 root 開始遍歷，每次比較當前兩個 nodes 的左右子點是否相等即可。

t1->left->val == t1->right->val && t1->right->val == t2->left->val。

完整程式碼:

class Solution {
public:
    bool dfs(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr && t2 == nullptr) { return true; }
        if (t1 == nullptr || t2 == nullptr) { return false; }
        return (t1->val == t2->val) && dfs(t1->left, t2->right) && dfs(t1->right, t2->left);
    }
    bool isSymmetric(TreeNode* root) {
        return dfs(root, root);   
    }
};