对称二叉树

每日第二题

对称二叉树

跳转链接

解题思路

func isSymmetric(root *TreeNode) bool {
	  
}

虽然这里是判断树是否是对称二叉树，但是也可以看成是判断两个树是否相等。首先只有一个根结点的二叉树肯定是对称二叉树，那么我们只需要判断跟节点的左右子树是否是对称二叉树就可以了，如果让左子树不动，右子树镜像对称的话，那就直接判断左子树和镜像之后的右子树是否相等就可以了。那么我们怎么镜像右子树呢？实际上就是让树的左右节点互换就可以了。那么我们合并镜像对称、判断是否相等两个步骤，我们先来看下判断两个树是否相等的代码

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil{
        return true
    }
    if q==nil || p == nil{
        return false
    }
    return p.Val == q.Val && // 节点的值和递归代码进行合并
        isSameTree(p.Left,q.Left) && isSameTree(p.Right,q.Right)
}

因为我们不是判断左右子树是否相等了，而是判断左子树和镜像右子树是否相等，而镜像右子树又是左右节点互换，那么我们在判断的时候手动把替换的逻辑改掉。从 isSameTree(p.Left,q.Left) 判断左子树的左节点和右子树的左节点相等换为isSameTree(p.Left,q.Right)就可以了。

最终答案

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }

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

func isSymmetricHelper(left,right *TreeNode) bool {
    if left == nil || right == nil{
        return left == right
    }
    if left.Val != right.Val{
        return false
    }
    return isSymmetricHelper(left.Left,right.Right) && 
        isSymmetricHelper(left.Right,right.Left)
}

写在最后

中午有了点时间，再做一道。