对称的二叉树

1. 题目描述

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

2. 思路

• 递归

3. 实现

• java

class TreeNode
{
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val)
    {
        this.val = val;

    }

}

public class 对称的二叉树
{
    boolean isSymmetrical(TreeNode pRoot)
    {
        //检查是否为空返回true
        if (pRoot == null)
        {
            return true;
        }

        return this.isSymmetricalRecursively(pRoot.left, pRoot.right);

    }

    private boolean isSymmetricalRecursively(TreeNode left, TreeNode right)
    {
        //左节点和右节点都为空那么返回true
        if (left == null && right == null)
        {
            return true;
        }
        //左节点或右节点有一个为空那么返回false
        if (left == null || right == null)
        {
            return false;
        }
        //左节点val==右节点val 并且
        return left.val == right.val
                // 左节点的左子树==右节点的右子树 并且
                && this.isSymmetricalRecursively(left.left, right.right)
                // 左节点的右子树==右节点的左子树
                && this.isSymmetricalRecursively(left.right, right.left);
    }
}

• go

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param pRoot TreeNode类
 * @return bool布尔型
 */
//时间复杂度：O(N)
//空间复杂度：O(N),最坏情况下，二叉树退化为链表
func isSymmetrical(pRoot *TreeNode) bool {
	if pRoot == nil {
		return true
	}
	
	return symmetrical(pRoot.Left, pRoot.Right) 
}

func symmetrical(left *TreeNode, right *TreeNode) bool {
	if left == nil && right == nil {
		return true
	}
	if left == nil || right == nil {
		return false
	}

	return left.Val == right.Val && symmetrical(left.Left, right.Right) && symmetrical(left.Right, right.Left)
}

4. 参考

• 对称的二叉树_牛客网
• Symmetric Tree - LeetCode