剑指 Offer 28. 对称的二叉树

剑指offer最优解免费

本问题对应的 leetcode 原文链接：剑指 Offer 28. 对称的二叉树

问题描述

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

限制：

0 <= 节点个数 <= 1000

解题思路

视频讲解直达：本题视频讲解

代码实现

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)){
            return true;
        }

        return f(root.left, root.right);
    }
    // 判断B是不是以A阶段为根节点的子树
    public boolean f(TreeNode A, TreeNode B){
        if(A == null && B == null){
            return true;
        }

        if(A == null || B == null){
            return false;
        }

        if(A.val != B.val){
            return false;
        }

        return f(A.left, B.right) && f(A.right, B.left);
    }
}

时间复杂度：O(n)
空间复杂度：树的高度

Python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root or (not root.left and not root.right):
            return True

        return self.f(root.left, root.right)

    # 判断B是不是以A阶段为根节点的子树
    def f(self, A, B):
        if not A and not B:
            return True

        if not A or not B:
            return False

        if A.val != B.val:
            return False

        return self.f(A.left, B.right) and self.f(A.right, B.left)

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root || (!root->left && !root->right)) {
            return true;
        }

        return f(root->left, root->right);
    }

    // 判断B是不是以A阶段为根节点的子树
    bool f(TreeNode* A, TreeNode* B) {
        if (!A && !B) {
            return true;
        }

        if (!A || !B) {
            return false;
        }

        if (A->val != B->val) {
            return false;
        }

        return f(A->left, B->right) && f(A->right, B->left);
    }
};

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    if root == nil || (root.Left == nil && root.Right == nil) {
        return true
    }

    return f(root.Left, root.Right)
}

// 判断B是不是以A阶段为根节点的子树
func f(A *TreeNode, B *TreeNode) bool {
    if A == nil && B == nil {
        return true
    }

    if A == nil || B == nil {
        return false
    }

    if A.Val != B.Val {
        return false
    }

    return f(A.Left, B.Right) && f(A.Right, B.Left)
}

JS

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (root == null || (root.left == null && root.right == null)) {
        return true;
    }

    return f(root.left, root.right);
};
// 判断 B 是不是以 A 阶段为根节点的子树
var f = function(A, B) {
    if (A == null && B == null) {
        return true;
    }

    if (A == null || B == null) {
        return false;
    }

    if (A.val !== B.val) {
        return false;
    }

    return f(A.left, B.right) && f(A.right, B.left);
};

剑指offer题解

Code

“`C++ []

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode root) {
if(root nullptr) return true;
if(root->left nullptr && root->right nullptr) return true;
return f(root->left,root->right);

}

public:
bool f(TreeNode* A,TreeNode* B){
if(Anullptr && Bnullptr) return true;
if(A nullptr || B nullptr) return false;
if(A->val != B->val) return false;

return f(A->left,B->right) && f(A->right,B->left); }

};

“`

发表回复取消回复

后才能评论

往远处看普通 2023年9月8日下午11:22
Problem: 剑指 Offer 28. 对称的二叉树

[TOC]

思路

通过递归方式将两边子树都往下递归，知道递归到两边的叶子节点，执行到这一步 ANULL && B NULL 结束循环返回 true 如果不是对称二叉树则返回false

解题方法

两个递归调用

复杂度

o(n)
– 时间复杂度:

添加时间复杂度, 示例： $O(n)$
- 空间复杂度:
  > 树的高度
Code

“`C++ []

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode root) {
if(root nullptr) return true;
if(root->left nullptr && root->right nullptr) return true;
return f(root->left,root->right);
```
}
```
public:
bool f(TreeNode* A,TreeNode* B){
if(Anullptr && Bnullptr) return true;
if(A nullptr || B nullptr) return false;
if(A->val != B->val) return false;
```
    return f(A->left,B->right) && f(A->right,B->left);
}
```
};

“`
登录以回复

优秀市民普通 2022年10月28日下午9:37

class Solution {
  public boolean is Symmetric(TreeNode root){
    return root == null ? true : recur(root.left,root.right);
  }

  public recur(TreeNode L, treeNode R){
    if(L == null && R == null)
      return true;
    if(L == null || R == null || L.val != R.val)
      return false;
    return recur(L.left, R.right) && recur(L.right, R.left);
  }
}

根据若两个树互为镜像满足的特点，考虑从根结点开始递归，判断每对节点是否对称

思路

解题方法

复杂度

Code