剑指Offer（五十八）：对称的二叉树

2018年1月26日11:02:40 4 5,683 °C
摘要

请实现一个函数，用来判断一颗二叉树是不是对称的。

剑指Offer（五十八）：对称的二叉树

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

1、思路

剑指Offer（五十八）：对称的二叉树

我们通常有三种不同的二叉树遍历算法，即前序遍历、中序遍历和后序遍历。在这三种遍历算法中，都是先遍历左子结点再遍历右子结点。以前序遍历为例，我们可以定义一个遍历算法，先遍历右子结点再遍历左子结点，暂且称其为前序遍历的对称遍历。

遍历第一棵树，前序遍历的遍历序列为{8,6,5,7,6,7,5}，其对称遍历的遍历序列为{8,6,5,7,6,7,5}。

遍历第二颗树，前序遍历的遍历序列为{8,6,5,7,9,7,5}，其对称遍历的遍历序列为{8,9,5,7,6,7,5}。

可以看到，使用此方法可以区分前两棵树，第一棵树为对称树，第二颗树不是对称树。但是当使用此方法，你会发现第三颗树的前序遍历和对称前序遍历的遍历序列是一样的。

怎么区分第三颗树呢？解决办法就是我们也要考虑NULL指针。此时，前序遍历的遍历序列{7,7,7,NULL,NULL,7,NULL,NULL,7,7,NLL,NULL,NULL}，其对称遍历的遍历序列为{7,7,NULL,7,NULL,NULL,7,7,NULL,NULL,7,NULL,NULL}。因为两种遍历的序列不同，因此这棵树不是对称树。

2、代码

C++：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(pRoot == NULL){
            return true;
        }
        return isSymmetriacalCor(pRoot, pRoot);
    }
private:
    bool isSymmetriacalCor(TreeNode* pRoot1, TreeNode* pRoot2){
        if(pRoot1 == NULL && pRoot2 == NULL){
            return true;
        }
        if(pRoot1 == NULL || pRoot2 == NULL){
            return false;
        }
        if(pRoot1->val != pRoot2->val){
            return false;
        }
        return isSymmetriacalCor(pRoot1->left, pRoot2->right) && isSymmetriacalCor(pRoot1->right, pRoot2->left);
    }
};

Python：

感谢@小小毛提供python代码记本地测试用例。

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def isSymmetrical(self, pRoot):
        # write code here
        if not pRoot:
            return True
        return self.recursiveTree(pRoot.left, pRoot.right)
 
    def recursiveTree(self, left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        if left.val == right.val:
            return self.recursiveTree(left.left, right.right) and self.recursiveTree(left.right, right.left)
        return False
if __name__=='__main__':
 
    A1 = TreeNode(1)
    A2 = TreeNode(2)
    A3 = TreeNode(2)
    A4 = TreeNode(3)
    A5 = TreeNode(4)
    A6 = TreeNode(4)
    A7 = TreeNode(3)
 
    A1.left=A2
    A1.right=A3
    A2.left=A4
    A2.right=A5
    A3.left=A6
    A3.right=A7
 
 
    solution = Solution()
    ans=solution.isSymmetrical(A1)
    print(ans)

weinxin
微信公众号
分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论：4   其中：访客  3   博主  1

    • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3
      回复 2019年4月11日 下午2:51  沙发

      思路是，求解它的镜像树，然后判断它们是否相等。相等则为平衡二叉树，不相等就不是。

      • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3
        回复 2019年4月11日 下午4:40  板凳

        就把代码写到这里，还可以回过头看。python版
        # -*- coding:utf-8 -*-
        class TreeNode:
        def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        class Solution:
        def isSymmetrical(self, pRoot):
        # write code here
        if not pRoot:
        return True
        return self.recursiveTree(pRoot.left, pRoot.right)

        def recursiveTree(self, left, right):
        if not left and not right:
        return True
        if not left or not right:
        return False
        if left.val == right.val:
        return self.recursiveTree(left.left, right.right) and self.recursiveTree(left.right, right.left)
        return False
        if __name__==’__main__’:

        A1 = TreeNode(1)
        A2 = TreeNode(2)
        A3 = TreeNode(2)
        A4 = TreeNode(3)
        A5 = TreeNode(4)
        A6 = TreeNode(4)
        A7 = TreeNode(3)

        A1.left=A2
        A1.right=A3
        A2.left=A4
        A2.right=A5
        A3.left=A6
        A3.right=A7

        solution = Solution()
        ans=solution.isSymmetrical(A1)
        print(ans)

        • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3
          回复 2019年4月11日 下午4:42  地板

          欢迎各位优化代码哦

            • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点
              回复 2019年4月11日 下午5:25  1层

              @小小毛 太给力了，已经添加～