Symmetric Binary Tree

1. Problem Description

Implement a function to determine whether a binary tree is symmetric. A binary tree is defined as symmetric if it is identical to its mirror image.

2. Approach

• Recursion

3. Implementation

• 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)
    {
        // Return true if it is empty
        if (pRoot == null)
        {
            return true;
        }

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

    }

    private boolean isSymmetricalRecursively(TreeNode left, TreeNode right)
    {
        // If both the left and right nodes are empty, return true
        if (left == null && right == null)
        {
            return true;
        }
        // If either the left or right node is empty, return false
        if (left == null || right == null)
        {
            return false;
        }
        // left node val == right node val, and
        return left.val == right.val
                // left subtree of the left node == right subtree of the right node, and
                && this.isSymmetricalRecursively(left.left, right.right)
                // right subtree of the left node == left subtree of the right node
                && this.isSymmetricalRecursively(left.right, right.left);
    }
}

• go

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

/**
 * The class name, method name, and parameter names in the code have already been specified. Do not modify them; directly return the value required by the method.
 *
 * @param pRoot TreeNode class
 * @return bool
 */
// Time complexity: O(N)
// Space complexity: O(N), in the worst case when the binary tree degenerates into a linked list
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. References

• Symmetric Binary Tree - NowCoder
• Symmetric Tree - LeetCode