Hexo

2020-08-29

对称二叉树

###思路—分治法

如果满足条件的对称二叉树

其左子树的前序遍历 && 右子树的后序遍历

得到的列表必然完全相反

左子树进行前序遍历: pre_order = [2,3,5,6,4,7,8] 后序遍历：post_order = [8,7,4,6,5,3,2]

pre==post.reverse

###代码

按照总结的二叉树遍历模板

void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}

分别定义前序和后序遍历的函数

def pre_order(self,root,li):    # 二叉树的前序遍历
    if root:
        li.append(root.val)
        self.pre_order(root.left,li)
        self.pre_order(root.right,li)
    elif root == None:
        li.append(None)

def post_order(self,root,li):   # 二叉树的后序遍历
    if root:
        self.post_order(root.left,li)
        self.post_order(root.right,li)
        li.append(root.val)
    elif root == None:
        li.append(None)

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        pre = []     # 用来存左子树的前序遍历
        post = []     # 用来存右子树的后序遍历
        if root == None:   # 无根节点
            return True
        if root and root.left == None and root.right == None:  # 只有根节点
            return True

        if root and root.left and root.right:
            self.pre_order(root.left, pre)
            self.post_order(root.right, post)
            post.reverse()            # 将后序遍历的列表倒序
            if pre == post:
                return True
            else:
                return False