剑指 Offer 28 对称的二叉树

概述

https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/

https://leetcode.com/problems/symmetric-tree/

递归法（同时遍历左右子树）

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return helper(root, root);
    }

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

递归法（前序遍历与前序遍历的镜像）

如果该树是对称的，显然其前序遍历中 left 和 right 的顺序互调不影响遍历结果。

有没有可能存在相同而不对称的呢？这确实是个问题。。。

显然是有的啊，如下面这棵树：

        +----+                        
        | 1  |                        
        +----+                        
         /--\                         
       /-    -\                       
     --        --                     
+----+          +----+                
| 2  |          | 2  |                
+----+          +----+                
   -\             -\                  
     -\             -\                
       -----+         --+----+        
       |  3 |           | 3  |        
       +----+           +----+        

Links: sword-offer-28

未经允许，禁止转载，本文源站链接：https://iamazing.cn/