LeetCode hot 热题100 对称二叉树

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

思路

这段代码的目的是判断一棵二叉树是否是对称的。对称的定义是：一棵树的左子树和右子树是镜像对称的。

具体步骤：

1. 主函数 isSymmetric 调用辅助函数 cheak，比较根节点的左子树和右子树是否对称。

2. 辅助函数 cheak 递归地比较两个子树：

• 如果两个节点均为空，返回 true。

• 如果其中一个节点为空或者两个节点的值不同，返回 false。

• 如果两个节点值相同，则递归比较：

• 左子树的左子树和右子树的右子树。

• 左子树的右子树和右子树的左子树。

3. 递归结束时，如果所有对称节点都匹配，则返回 true。

运行步骤

假设有以下输入的二叉树：

       1

      / \

     2   2

    / \ / \

   3  4 4  3

1. 调用 isSymmetric 函数：

• 输入 root（根节点 1）。

• 调用 cheak(root->left, root->right)，即 cheak(2, 2)。

2. 第一次调用 cheak(2, 2)：

• 两个节点均不为空，且 left->val == right->val（均为 2）。

• 递归调用 cheak(2->left, 2->right) 和 cheak(2->right, 2->left)，即 cheak(3, 3) 和 cheak(4, 4)。

3. 第二次调用 cheak(3, 3)：

• 两个节点均不为空，且 left->val == right->val（均为 3）。

• 递归调用 cheak(3->left, 3->right) 和 cheak(3->right, 3->left)，即 cheak(nullptr, nullptr)。

• 返回 true，因为两侧均为空。

4. 第二次调用 cheak(4, 4)：

• 两个节点均不为空，且 left->val == right->val（均为 4）。

• 递归调用 cheak(4->left, 4->right) 和 cheak(4->right, 4->left)，即 cheak(nullptr, nullptr)。

• 返回 true，因为两侧均为空。

5. 返回结果：

• 所有递归调用均返回 true，表示这棵树是对称的。

最终，isSymmetric 返回 true。

代码逻辑解释

1. 入口：

• isSymmetric 是入口函数，直接判断树是否对称。

2. 递归条件：

• 如果左右子树都为空，返回 true。

• 如果一个为空或值不相等，返回 false。

• 如果值相等，则继续递归判断其子树。

3. 递归结束：

• 当遍历到叶子节点（空节点）时，递归结束，逐步返回结果。

如果有其他问题，随时告诉我！

原文地址：https://blog.csdn.net/qq_51956059/article/details/145300883

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！