剑指 Offer 28 对称的二叉树

Tag: 剑指-Offer Posted on 2022-02-23 16:47:13 Edited on 2022-02-23 17:07:33 Views: 197

概述

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  |        
       +----+           +----+        

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